The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
Authors:
- Yair BartalYBYair Bartal
- Lee-Ad GottliebLGLee-Ad Gottlieb
- Robert KrauthgamerRKRobert Krauthgamer
- 1 January 2016
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 45 (4) , 1563-1581
Abstract
The traveling salesman problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem an algorithm that for any fixed $\varepsilon>0$ computes in randomized polynomial time a $(1+\varepsilon)$-approximation to the optimal tour in TSP instances that form an arbitrary metric space with bounded intrinsic dimension. The celebrated results of Arora [J. ACM, 45 (1998), pp. 753--782] and Mitchell [SIAM J. Comput., 28 (1999), pp. 1298--1309] 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 [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 281--290].
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Advances in metric embedding theoryAdvances in Mathematics, 2011
- 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
- PLANE WITH $A_{\infty}$ -WEIGHTED METRIC NOT BILIPSCHITZ EMBEDDABLE TO ${\bb R}^n$Bulletin of the London Mathematical Society, 2002
- 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
- Nearest Neighbor Queries in Metric SpacesDiscrete & Computational Geometry, 1999
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJournal of the ACM, 1998
- Plongements lipschitziens dans ${\bbfR}\sp n$Bulletin de la Société Mathématiques de France, 1983
- Solution of a Large-Scale Traveling-Salesman ProblemJournal of the Operations Research Society of America, 1954