Time : 11/24 2021 2:00 p.m
Venue : 清華大學台達 632 會議室
An adaptive algorithm for the exact Euclidean travling salesman problem with quadratic improvement
Abstract
de Berg [An ETH-tight exact algorithm for Euclidean TSP, 2018] solved the Euclidean traveling salesman problem (ETSP) with n points in R^d by deriving a divide-and-conquer algorithm with a running time of 2^O(n^(1-1/d)). Their algorithm is near optimal because algorithms with a time complexity of less than 2^o(n^(1-1/d)) do not exist unless ETH fails. This result leaves very little room for further improving ETSP algorithms. However, in this paper, we make a nontrivial modification to de Berg et al.’s algorithm that results in a quadratic speedup. Our technical contribution is an adaptive strategy that can balance the size of the divided subproblems with the complexity of merging them in each iteration.