Document Open Access Logo

The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem

Authors Ulrich A. Brodowsky, Stefan Hougardy

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.18.pdf
  • Filesize: 0.75 MB
  • 15 pages

Document Identifiers

Author Details

Ulrich A. Brodowsky
  • Pontsheide 20, 52076 Aachen, Germany
Stefan Hougardy
  • Research Institute for Discrete Mathematics, Universität Bonn, Germany

Funding

  • Hougardy, Stefan: funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy - EXC-2047/1 - 390685813.

Acknowledgements

We thank the anonymous referees for several useful comments.

Cite AsGet BibTex

Ulrich A. Brodowsky and Stefan Hougardy. The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.STACS.2021.18

Abstract

The 2-Opt heuristic is a simple improvement heuristic for the Traveling Salesman Problem. It starts with an arbitrary tour and then repeatedly replaces two edges of the tour by two other edges, as long as this yields a shorter tour. We will prove that for Euclidean Traveling Salesman Problems with n cities the approximation ratio of the 2-Opt heuristic is Θ(log n / log log n). This improves the upper bound of O(log n) given by Chandra, Karloff, and Tovey [Barun Chandra et al., 1999] in 1999.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • traveling salesman problem
  • metric TSP
  • Euclidean TSP
  • 2-Opt
  • approximation algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sanjeev Arora. Polynomial time approximation schemes for Euclidean Traveling Salesman and other geometric problems. Journal of the ACM, 45(5):753-782, September 1998. Google Scholar
  2. Jon Jouis Bentley. Fast algorithms for geometric Traveling Salesman Problems. ORSA Journal on Computing, 4(4):387-411, 1992. Google Scholar
  3. Barun Chandra, Howard Karloff, and Craig Tovey. New results on the old k-opt algorithm for the Traveling Salesman Problem. SIAM J. Comput, 28(6):1998-2029, 1999. Google Scholar
  4. Nicos Christofides. Worst-case analysis of a new heuristic for the Travelling Salesman Problem. Technical Report 388, Carnegie-Mellon University, 1976. Google Scholar
  5. Matthias Englert, Heiko Röglin, and Berthold Vöcking. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica, 68:190-264, 2014. Google Scholar
  6. Merrill M. Flood. The traveling-salesman problem. Operations Research, 4(1):61-75, 1956. Google Scholar
  7. Michael R. Garey and David S. Johnson. Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979. Google Scholar
  8. Stefan Hougardy, Fabian Zaiser, and Xianghui Zhong. The approximation ratio of the 2-Opt Heuristic for the metric Traveling Salesman Problem. Operations Research Letters, 48:401-404, 2020. Google Scholar
  9. Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric TSP. arXiv:2007.01409v1 [cs.DS], July 2020. URL: http://arxiv.org/abs/2007.01409v1.
  10. Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, and Umesh Vazirani. On syntactic versus computational views of approximability. SIAM J. Comput., 28:164-191, 1998. Google Scholar
  11. Joseph 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. Google Scholar
  12. Christos H. Papadimitriou. The Euclidean Traveling Salesman Problem is NP-complete. Theoretical Computer Science, 4(3):237-244, June 1977. Google Scholar
  13. Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. Journal of the ACM, 23(3):555-565, July 1976. Google Scholar
  14. A.I. Serdyukov. O nekotorykh ekstremal'nykh obkhodakh v grafakh. Upravlyaemye sistemy, 17:76-79, 1978. Google Scholar
  15. Xianghui Zhong. Approximation Algorithms for the Traveling Salesman Problem. PhD thesis, Research Institute for Discrete Mathematics, University of Bonn, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact