The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
Preprint
Abstract
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+eps)-approximation to the optimal tour, for any fixed eps>0, in TSP instances that form an arbitrary metric space with bounded intrinsic dimension. The celebrated results of Arora (A-98) and Mitchell (M-99) 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 (T-04).Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling MetricsDiscrete & Computational Geometry, 2011
- A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median ProblemSIAM Journal on Computing, 2007
- Bilipschitz Embeddings of Metric Spaces into Space FormsGeometriae Dedicata, 2001
- Ahlfors Q -regular spaces with arbitrary Q > 1 admitting weak Poincaré inequalityGeometric and Functional Analysis, 2000
- When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner TreeSIAM Journal on Computing, 2000
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJournal of the ACM, 1998
- The Traveling Salesman Problem with Distances One and TwoMathematics of Operations Research, 1993
- The Euclidean travelling salesman problem is NP-completeTheoretical Computer Science, 1977