A Gap-ETH-Tight Approximation Scheme for Euclidean TSP

Sándor Kisfaludi-Bak, Jesper Nederlof, Karol Węgrzycki

We revisit the classic task of finding the shortest tour of $n$ points in $d$-dimensional Euclidean space, for any fixed constant $d\ge 2$. We determine the optimal dependence on…