More Web Proxy on the site http://driver.im/

research-article

The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme

Authors:

Lee-Ad Gottlieb,

Robert KrauthgamerAuthors Info & Claims

STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

Pages 663 - 672

https://doi.org/10.1145/2213977.2214038

Published: 19 May 2012 Publication History

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+µ)-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].

Supplementary Material

JPG File (stoc_8a_1.jpg)

Download
11.29 KB

MP4 File (stoc_8a_1.mp4)

Download
135.86 MB

References

[1]

D. L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook. The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). Princeton University Press, Princeton, NJ, USA, 2007.

Digital Library

[2]

I. Abraham, Y. Bartal, and O. Neiman. Embedding metric spaces in their intrinsic dimension. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 363--372, 2008.

Digital Library

[3]

I. Abraham, Y. Bartal, and O. Neiman. Advances in metric embedding theory. Advances in Mathematics}, 228(6):3026 -- 3126, 2011.

[4]

I. Abraham, S. Chechik, C. Gavoille, and D. Peleg. Forbidden-set distance labels for graphs of bounded doubling dimension. In 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 192--200. ACM, 2010.

Digital Library

[5]

S. Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM, 45:753--782, 1998.

Digital Library

[6]

S. Arora, P. Raghavan, and S. Rao. Approximation schemes for euclidean k-medians and related problems. In 30th annual ACM symposium on Theory of computing, pages 106--113. ACM, 1998.

Digital Library

[7]

P. Assouad. Plongements lipschitziens dans R spn. Bull. Soc. Math. France, 111(4):429--448, 1983.

[8]

Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science, pages 184--193. IEEE Computer Society, 1996.

Digital Library

[9]

Y. Bartal. On approximating arbitrary metrices by tree metrics. In 30th annual ACM symposium on Theory of computing, pages 161--168. ACM, 1998.

Digital Library

[10]

Y. Bartal, B. Recht, and L. J. Schulman. Dimensionality reduction: beyond the johnson-lindenstrauss bound. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11, pages 868--887. SIAM, 2011.

Digital Library

[11]

T.-H. H. Chan and K. M. Elbassioni. A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics. Discrete & Computational Geometry, 46(4):704--723, 2011.

Digital Library

[12]

R. Cole and L.-A. Gottlieb. Searching dynamic point sets in spaces with bounded doubling dimension. In 38th annual ACM symposium on Theory of computing, pages 574--583, 2006.

Digital Library

[13]

T.-H. H. Chan and A. Gupta. Approximating {TSP} on metrics with bounded global growth. In 19th annual ACM-SIAM symposium on Discrete algorithms, pages 690--699. SIAM, 2008.

Digital Library

[14]

T.-H. H. Chan, A. Gupta, and K. Talwar. Ultra-low-dimensional embeddings for doubling metrics. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms}, SODA '08, pages 333--342. Society for Industrial and Applied Mathematics, 2008.

Digital Library

[15]

N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, Carnegie-Mellon Univ. Management Sciences Research Group, 1976.

[16]

A. Czumaj and A. Lingas. A polynomial time approximation scheme for euclidean minimum cost k-connectivity. In 25th International Colloquium on Automata, Languages and Programming, ICALP '98, pages 682--694. Springer-Verlag, 1998.

Digital Library

[17]

K. L. Clarkson. Nearest neighbor queries in metric spaces. Discrete Comput. Geom.}, 22(1):63--93, 1999.

[18]

A. Czumaj, A. Lingas, and H. Zhao. Polynomial-time approximation schemes for the euclidean survivable network design problem. In 29th International Colloquium on Automata, Languages and Programming, ICALP '02, pages 973--984. Springer-Verlag, 2002.

Digital Library

[19]

J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In 35th annual ACM symposium on Theory of computing, pages 448--455. ACM, 2003.

Digital Library

[20]

J. Gao, L. J. Guibas, and A. Nguyen. Deformable spanners and applications. Comput. Geom. Theory Appl., 35(1), 2006.

Digital Library

[21]

L.-A. Gottlieb and R. Krauthgamer. A nonlinear approach to dimension reduction. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11, pages 888--899. SIAM, 2011.

Digital Library

[22]

L.-A. Gottlieb, L. Kontorovich, and R. Krauthgamer. Efficient classification for metric data. In 23rd Conference on Learning Theory}, pages 433--440. Omnipress, 2010.

[23]

A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS '03, pages 534--543. IEEE Computer Society, 2003.

Digital Library

[24]

G. Gutin and A. P. Punnen, editors. The traveling salesman problem and its variations, volume 12 of Combinatorial Optimization. Kluwer Academic Publishers, Dordrecht, 2002.

Digital Library

[25]

L.-A. Gottlieb and L. Roditty. An optimal dynamic spanner for doubling metric spaces. In Proceedings of the 16th annual European symposium on Algorithms, ESA '08, pages 478--489. Springer-Verlag, 2008.

Digital Library

[26]

R. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations. Plenum Press, 1972.

[27]

R. Krauthgamer and J. R. Lee. Navigating nets: {S}imple algorithms for proximity search. In 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 791--801, January 2004.

Digital Library

[28]

S. G. Kolliopoulos and S. Rao. A nearly linear-time approximation scheme for the Euclidean k-median problem. SIAM J. Comput., 37:757--782, June 2007.

Digital Library

[29]

T. J. Laakso. Ahlfors Q-regular spaces with arbitrary Q>1 admitting weak Poincar'e inequality. Geom. Funct. Anal.}, 10(1):111--123, 2000.

[30]

T. J. Laakso. Plane with A infty-weighted metric not bi-Lipschitz embeddable to B R sp N. Bull. London Math. Soc., 34(6):667--676, 2002.

[31]

J. R. Lee. The Godel prize, TSP, and volume growth (blog post). http://tcsmath.wordpress.com/2010/06/24/the-godel-prize-tsp-and-volume-growth, June 2010.

[32]

E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, and D. B. Shmoys, editors. The Traveling Salesman Problem. Wiley-Interscience series in discrete mathematics, 1985.

[33]

U. Lang and C. Plaut. Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata, 87(1--3):285--307, 2001.

[34]

J. S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric {TSP}, k-MST, and related problems. SIAM J. Comput., 28(4):1298--1309, 1999.

Digital Library

[35]

J. S. B. Mitchell. A PTAS for TSP with neighborhoods among fat regions in the plane. In 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 11--18. SIAM, 2007.

Digital Library

[36]

C. H. Papadimitriou. The Euclidean travelling salesman problem is NP-complete. Theoretical Computer Science, 4(3):237 -- 244, 1977.

[37]

C. Papadimitriou and S. Vempala. On the approximability of the traveling salesman problem. Combinatorica, 26:101--120, 2006.

Digital Library

[38]

C. H. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Math. Oper. Res., 18:1--11, February 1993.

Digital Library

[39]

G. Reinelt. The Traveling Salesman, volume 840 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1994.

[40]

S. B. Rao and W. D. Smith. Approximating geometrical graphs via "spanners" and "banyans". In 30th annual ACM symposium on Theory of computing, pages 540--550. ACM, 1998.

Digital Library

[41]

M. Smid. On some combinatorial problems in metric spaces of bounded doubling dimension. Manuscript, available at http://people.scs.carleton.ca/ michiel/research.html, 2010.

[42]

K. Talwar. Bypassing the embedding: algorithms for low dimensional metrics. In 36th annual ACM symposium on Theory of computing, pages 281--290. ACM, 2004.

Digital Library

[43]

L. Trevisan. When Hamming meets Euclid: The approximability of geometric TSP and Steiner tree. SIAM Journal on Computing, 30(2):475--485, 2000.

Digital Library

Cited By

Khachay MNeznakhina ERyzhenko K(2023)Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman ProblemProceedings of the Steklov Institute of Mathematics10.1134/S0081543822060128319:S1(S140-S155)Online publication date: 16-Feb-2023
https://doi.org/10.1134/S0081543822060128
Sidiropoulos ASinghal KSridhar V(2021)Fractal Dimension and Lower Bounds for Geometric ProblemsDiscrete & Computational Geometry10.1007/s00454-021-00282-8Online publication date: 28-May-2021
https://doi.org/10.1007/s00454-021-00282-8
Disser YFeldmann AKlimm MKönemann J(2021)Travelling on Graphs with Small Highway DimensionAlgorithmica10.1007/s00453-020-00785-5Online publication date: 12-Feb-2021
https://doi.org/10.1007/s00453-020-00785-5
Show More Cited By

Index Terms

The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Traveling salesman problem under categorization

We introduce two new classes of traveling salesman problems (TSP1 and TSP2) which subsume the classical traveling salesman problem and the bottleneck traveling salesman problem. It is shown that these problems are strongly NP-complete on Halin graphs ...
Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey

The traveling salesman problem (TSP) belongs to the most basic, most important, and most investigated problems in combinatorial optimization. Although it is an ${\cal NP}$-hard problem, many of its special cases can be solved efficiently in polynomial ...
Labeled Traveling Salesman Problems: Complexity and approximation

We consider labeled Traveling Salesman Problems, defined upon a complete graph of n vertices with colored edges. The objective is to find a tour of maximum or minimum number of colors. We derive results regarding hardness of approximation and analyze ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

May 2012

1310 pages

ISBN:9781450312455

DOI:10.1145/2213977

General Chair:
Howard Karloff
AT&T Labs--Research
,
Program Chair:
Toniann Pitassi
University of Toronto

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'12

Sponsor:

SIGACT

STOC'12: Symposium on Theory of Computing

May 19 - 22, 2012

New York, New York, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
126
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)1

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khachay MNeznakhina ERyzhenko K(2023)Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman ProblemProceedings of the Steklov Institute of Mathematics10.1134/S0081543822060128319:S1(S140-S155)Online publication date: 16-Feb-2023
https://doi.org/10.1134/S0081543822060128
Sidiropoulos ASinghal KSridhar V(2021)Fractal Dimension and Lower Bounds for Geometric ProblemsDiscrete & Computational Geometry10.1007/s00454-021-00282-8Online publication date: 28-May-2021
https://doi.org/10.1007/s00454-021-00282-8
Disser YFeldmann AKlimm MKönemann J(2021)Travelling on Graphs with Small Highway DimensionAlgorithmica10.1007/s00453-020-00785-5Online publication date: 12-Feb-2021
https://doi.org/10.1007/s00453-020-00785-5
Gimadi ERykov ITsidulko O(2020)On PTAS for the Geometric Maximum Connected k-Factor ProblemOptimization and Applications10.1007/978-3-030-38603-0_15(194-205)Online publication date: 8-Jan-2020
https://doi.org/10.1007/978-3-030-38603-0_15
Disser YFeldmann AKlimm MKönemann J(2019)Travelling on Graphs with Small Highway DimensionGraph-Theoretic Concepts in Computer Science10.1007/978-3-030-30786-8_14(175-189)Online publication date: 12-Sep-2019
https://doi.org/10.1007/978-3-030-30786-8_14
Abdoun OMoumen YDaanoun A(2019)A Parallel Approach to Optimize the Supply Chain ManagementAdvanced Intelligent Systems for Sustainable Development (AI2SD’2018)10.1007/978-3-030-11881-5_12(129-146)Online publication date: 14-Feb-2019
https://doi.org/10.1007/978-3-030-11881-5_12
Wang YRemmel J(2018)A Method to Compute the Sparse Graphs for Traveling Salesman Problem Based on Frequency QuadrilateralsFrontiers in Algorithmics10.1007/978-3-319-78455-7_22(286-299)Online publication date: 21-Mar-2018
https://doi.org/10.1007/978-3-319-78455-7_22
Moumen YAbdoun ODaanoun AZbitou JLarbi SEl Mokhtar E(2017)Parallel approach for genetic algorithm to solve the Asymmetric Traveling Salesman ProblemsProceedings of the 2nd International Conference on Computing and Wireless Communication Systems10.1145/3167486.3167510(1-6)Online publication date: 14-Nov-2017
https://dl.acm.org/doi/10.1145/3167486.3167510
Zheng HWu J(2017)Cooperative Wireless Charging Vehicle Scheduling2017 IEEE 14th International Conference on Mobile Ad Hoc and Sensor Systems (MASS)10.1109/MASS.2017.13(224-232)Online publication date: Oct-2017
https://doi.org/10.1109/MASS.2017.13
Chan TJiang S(2016)Reducing curse of dimensionalityProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884489(754-765)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884489
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents