An ETH-Tight Exact Algorithm for Euclidean TSP
share
We study exact algorithms for Euclidean TSP in R^d. In the early 1990s algorithms with n^O(√(n)) running time were presented for the planar case, and some years later an algorithm with n^O(n^1-1/d) running time was presented for any d≥ 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Euclidean TSP, except for a lower bound stating that the problem admits no 2^O(n^1-1/d-ϵ) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a 2^O(n^1-1/d) algorithm and by showing that an 2^o(n^1-1/d) algorithm does not exist unless ETH fails.
READ FULL TEXT