The Traveling Salesman Problem: Low-dimensionality Implies a Polynomial Time Approximation Scheme
Yair Bartal, Lee-Ad J. Gottlieb, Robert Krauthgamer · 2013
The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1 + ε)-approximation to the optimal tour, for any fixed ε> 0, in TSP instances that form an arbitrary metric space with bounded intrinsic dimension. The celebrated results of Arora [Aro98] and Mitchell [Mit99] prove that the above result holds in the special case of TSP in a fixed-dimensional Euclidean space. Thus, our algorithm demonstrates that the algorithmic tractability of metric TSP depends on the dimensionality of the space and not on its specific geometry. This result resolves a problem that has been open since the quasi-polynomial time algorithm of Talwar [Tal04].