An ETH-Tight Exact Algorithm for Euclidean TSP
Publication date
2018
Authors
Berg, Mark de
Bodlaender, Hans
Kisfaludi-Bak, Sándor
Kolay, Sudeshna
Editors
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
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(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 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(n1-1/d) algorithm and by showing that a 2 o(n1-1/d) algorithm does not exist unless ETH fails.
Keywords
Particle separators, Approximation algorithms, Computer science, Complexity theory, Hypercubes, Heuristic algorithms, Taverne
Citation
Berg, M D, Bodlaender, H L, Kisfaludi-Bak, S & Kolay, S 2018, An ETH-Tight Exact Algorithm for Euclidean TSP. in Proceedings 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018. IEEE, pp. 450-461. https://doi.org/10.1109/FOCS.2018.00050