2024/11/04 by Mömke, Tobias, Zhou, Hang
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2411.02585
The Traveling Salesman Problem (TSP) in the d-dimensional Euclidean space is among the oldest and most famous NP-hard optimization problems. In breakthrough works, Arora [J. ACM 1998] and Mitchell [SICOMP 1999] gave the first polynomial time approximation schemes. To improve the running time, Rao and Smith [STOC 1998] gave a randomized (1/ε)^O(1/εd-1)⋅ nlog n time approximation scheme. Bartal and Gottlieb [FOCS 2013] gave a randomized approximation scheme in 2^(1/ε)O(d) n time, which is linear in n. Recently, Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS 2021] gave a randomized approximation scheme in 2^O(1/εd-1) n log n time, achieving a Gap-ETH tight dependence on ε. It is raised as a challenging open question by Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS 2021] whether a running time of 2^O(1/εd-1)n is achievable. We answer their question positively by giving a randomized 2^O(1/εd-1) n time approximation scheme for Euclidean TSP.