A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP

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\mathrm{/}\epsilon {)}^{O(1\mathrm{/}{\epsilon }^{d-1})}\cdot n\log n$ time approximation scheme. Bartal and Gottlieb [FOCS 2013] gave a randomized approximation scheme in $2^{(1\mathrm{/}\epsilon {)}^{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\mathrm{/}{\epsilon }^{d-1})}n\log n$ time, achieving a Gap-ETH tight dependence on $\epsilon$. 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\mathrm{/}{\epsilon }^{d-1})}n$ is achievable. We answer their question positively by giving a randomized $2^{O(1\mathrm{/}{\epsilon }^{d-1})}n$ time approximation scheme for Euclidean TSP.