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

Tobias Mömke, Hang Zhou

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…