A Linear Time Approximation Scheme for Euclidean TSP

The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. The special case of TSP in bounded-dimensional Euclidean spaces has been a particular focus of research: The celebrated results of Arora [Aro98] and Mitchell [Mit99] - along with subsequent improvements of Rao and Smith [RS98] - demonstrated a polynomial time approximation scheme for this problem, ultimately achieving a runtime of O_d,ε(n log n). In this paper, we present a linear time approximation scheme for Euclidean TSP, with runtime O_d,ε(n). This improvement resolves a 15 year old conjecture of Rao and Smith, and matches for Euclidean spaces the bound known for a broad class of planar graphs [Kle08].