An ETH-tight Exact Algorithm for Euclidean TSP
Publication date
2023-06-30
Authors
de Berg, Mark
Bodlaender, Hans
Kisfaludi-Bak, Sándor
Kolay, Sudeshna
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
taverne
Abstract
We study exact algorithms for Metric TSP in ℝd. In the early 1990s, algorithms with (Formula Presented) running time were presented for the planar case, and some years later an algorithm with (Formula Presnted) running time was presented for any d\geqslant 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Metric TSP, except for a lower bound stating that the problem admits no (Formula Presented) algorithm unless ETH fails. In this paper we settle the complexity of Metric TSP, up to constant factors in the exponent and under ETH, by giving an algorithm with running time (Formula Presented).
Keywords
Euclidean traveling salesman, separator theroem, subexponential algorithm, Taverne, General Computer Science, General Mathematics
Citation
de Berg, M, Bodlaender, H L, Kisfaludi-Bak, S & Kolay, S 2023, 'An ETH-tight Exact Algorithm for Euclidean TSP', SIAM Journal on Computing, vol. 52, no. 3, pp. 740-760. https://doi.org/10.1137/22M1469122