Time : 11/16 2021 10:00 a.m
Venue: 資訊所新館 106 會議室
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.