An ETH-Tight Exact Algorithm for Euclidean TSP
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Sudeshna Kolay · 2018
We study exact algorithms for Euclidean TSP in Rd. In the early 1990s algorithms with nO(√n)running time were presented for the planar case, and some years later an algorithm with nO(n1-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 2O(n1-1/d-ε) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a 2O(n1-1/d)algorithm and by showing that a 2o(n1-1/d)algorithm does not exist unless ETH fails.