TY - JOUR
T1 - An ETH-tight Exact Algorithm for Euclidean TSP
AU - de Berg, Mark
AU - Bodlaender, Hans L.
AU - Kisfaludi-Bak, Sándor
AU - Kolay, Sudeshna
N1 - Funding Information:
*Received by the editors January 4, 2022; accepted for publication (in revised form) February 6, 2023; published electronically June 5, 2023. An earlier version of this article appeared in the Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, IEEE Computer Society, 2018, pp. 450--461, and the article shares content with the third author's thesis prepared at Technische Universiteit Eindhoven, Department of Mathematics and Computer Science, 2019. https://doi.org/10.1137/22M1469122 Funding: This work was supported by the NETWORKS project funded by the Netherlands Organization for Scientific Research under grant 024.002.003. \dagger Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven 5600 MB, The Netherlands ([email protected]). \ddagger Department of Computer Science, Utrecht University, Utrecht 3508 TB, The Netherlands ([email protected]). \S Department of Computer Science, Aalto University, Espoo FI-00076, Finland ([email protected]). \P Indian Institute of Technology Kharagpur, Kharagpur, India ([email protected]).
Publisher Copyright:
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
PY - 2023/6/30
Y1 - 2023/6/30
N2 - 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).
AB - 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).
KW - Euclidean traveling salesman
KW - separator theroem
KW - subexponential algorithm
UR - http://www.scopus.com/inward/record.url?scp=85165727857&partnerID=8YFLogxK
U2 - 10.1137/22M1469122
DO - 10.1137/22M1469122
M3 - Article
AN - SCOPUS:85165727857
SN - 0097-5397
VL - 52
SP - 740
EP - 760
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 3
ER -