Document Open Access Logo

New Approximation Algorithms for (1,2)-TSP

Authors Anna Adamaszek, Matthias Mnich , Katarzyna Paluch

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.9.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Anna Adamaszek
  • University of Copenhagen, Denmark
Matthias Mnich
  • Universität Bonn, Germany , and Maastricht University, The Netherlands
Katarzyna Paluch
  • Wroclaw University, Poland

Funding

  • Mnich, Matthias: Supported by ERC Starting Grant 306465 (BeyondWorstCase) and DFG grant MN 59/4-1.
  • Paluch, Katarzyna: Supported by Polish National Science Center grant UMO-2013/11/B/ST6/01748.

Cite AsGet BibTex

Anna Adamaszek, Matthias Mnich, and Katarzyna Paluch. New Approximation Algorithms for (1,2)-TSP. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.9

Abstract

We give faster and simpler approximation algorithms for the (1,2)-TSP problem, a well-studied variant of the traveling salesperson problem where all distances between cities are either 1 or 2. Our main results are two approximation algorithms for (1,2)-TSP, one with approximation factor 8/7 and run time O(n^3) and the other having an approximation guarantee of 7/6 and run time O(n^{2.5}). The 8/7-approximation matches the best known approximation factor for (1,2)-TSP, due to Berman and Karpinski (SODA 2006), but considerably improves the previous best run time of O(n^9). Thus, ours is the first improvement for the (1,2)-TSP problem in more than 10 years. The algorithm is based on combining three copies of a minimum-cost cycle cover of the input graph together with a relaxed version of a minimum weight matching, which allows using "half-edges". The resulting multigraph is then edge-colored with four colors so that each color class yields a collection of vertex-disjoint paths. The paths from one color class can then be extended to an 8/7-approximate traveling salesperson tour. Our algorithm, and in particular its analysis, is simpler than the previously best 8/7-approximation. The 7/6-approximation algorithm is similar and even simpler, and has the advantage of not using Hartvigsen's complicated algorithm for computing a minimum-cost triangle-free cycle cover.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Approximation algorithms
  • traveling salesperson problem
  • cycle cover

Metrics

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

References

  1. Eric Angel, Evripidis Bampis, and Laurent Gourvès. Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem. Theoret. Comput. Sci., 310(1):135-146, 2004. Google Scholar
  2. Eric Angel, Evripidis Bampis, Laurent Gourvès, and Jérôme Monnot. (Non)-approximability for the multi-criteria TSP(1,2). In Proc. FCT 2005, volume 3623 of Lecture Notes Comput. Sci., pages 329-340, 2005. Google Scholar
  3. Sanjeev Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In Proc. FOCS 1996, pages 2-11. IEEE Computer Society, 1996. URL: http://dx.doi.org/10.1109/SFCS.1996.548458.
  4. Piotr Berman and Marek Karpinski. 8/7-approximation algorithm for (1,2)-TSP. In Proc. SODA 2006, pages 641-648, 2006. Google Scholar
  5. M. Bläser and L. Shankar Ram. An improved approximation algorithm for TSP with distances one and two. In Proc. FCT 2005, volume 3623 of LNCS, pages 504-515. Springer, 2005. URL: http://dx.doi.org/10.1007/11537311_44.
  6. Markus Bläser. A 3/4-approximation algorithm for maximum ATSP with weights zero and one. In Proc. APPROX-RANDOM 2004, volume 3122 of Lecture Notes Comput. Sci., pages 61-71. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-27821-4_6.
  7. Markus Bläser and Bodo Manthey. Approximating maximum weight cycle covers in directed graphs with weights zero and one. Algorithmica, 42(2):121-139, 2005. Google Scholar
  8. Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem, 1976. TR 388, Graduate School of Industrial Administration, CMU. Google Scholar
  9. Szymon Dudycz, Jan Marcinkowski, Katarzyna Paluch, and Bartosz Rybicki. A 4/5-Approximation Algorithm for the Maximum Traveling Salesman Problem, volume 10328 of Lecture Notes Comput. Sci., pages 173-185. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-59250-3_15.
  10. W. Fernandez de la Vega and M. Karpinski. On the approximation hardness of dense TSP and other path problems. Inform. Process. Lett., 70(2):53-55, 1999. Google Scholar
  11. Harold N. Gabow. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Proc. STOC 1983, pages 448-456, 1983. Google Scholar
  12. Mikael Gast, Matthias Hauptmann, and Marek Karpinski. Approximability of TSP on power law graphs. CoRR, abs/1509.03976, 2015. URL: http://arxiv.org/abs/1509.03976.
  13. David B. Hartvigsen. Personal communication. Google Scholar
  14. David B. Hartvigsen. Extensions of Matching Theory. PhD thesis, Carnegie-Mellon University, 1984. Google Scholar
  15. Michael Held and Richard M. Karp. The traveling-salesman problem and minimum spanning trees. Operations Res., 18:1138-1162, 1970. Google Scholar
  16. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85-103. Plenum, New York, 1972. Google Scholar
  17. Marek Karpinski, Michael Lampis, and Richard Schmied. New inapproximability bounds for TSP. In Proc. ISAAC 2013, volume 8283 of Lecture Notes Comput. Sci., pages 568-578. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-45030-3_53.
  18. Marek Karpinski and Richard Schmied. On approximation lower bounds for TSP with bounded metrics. Electr. Colloquium Computat. Complexity, 19:8, 2012. Google Scholar
  19. Marek Karpinski and Richard Schmied. Approximation hardness of graphic tsp on cubic graphs. RAIRO Oper. Res., 49(4):651-668, 2015. Google Scholar
  20. László Lovász and Michael D. Plummer. Matching theory. AMS Chelsea Publishing, Providence, RI, 2009. Corrected reprint of the 1986 original. Google Scholar
  21. Matthias Mnich and Tobias Mömke. Improved integrality gap upper bounds for traveling salesperson problems with distances one and two. European J. Oper. Res., 266(2):436-457, 2018. Google Scholar
  22. Katarzyna Paluch. Maximum ATSP with weights zero and one via half-edges. Theory Comput. Syst., 62(2):319-336, 2018. Google Scholar
  23. Katarzyna Paluch, Khaled Elbassioni, and Anke van Zuylen. Simpler approximation of the maximum asymmetric traveling salesman problem. In Proc. STACS 2012, volume 14 of Leibniz Int. Proc. Informatics, pages 501-506, 2012. Google Scholar
  24. Christos H. Papadimitriou and Mihalis Yannakakis. The traveling salesman problem with distances one and two. Math. Oper. Res., 18(1):1-11, 1993. Google Scholar
  25. Jiawei Qian, Frans Schalekamp, David P. Williamson, and Anke van Zuylen. On the integrality gap of the subtour LP for the 1,2-TSP. In Proc. LATIN 2012, volume 7256 of Lecture Notes Comput. Sci., pages 606-617, 2012. Google Scholar
  26. András Sebő and Jens Vygen. Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica, 34(5):597-629, 2014. Google Scholar
  27. Luca Trevisan. When Hamming meets Euclid: the approximability of geometric TSP and Steiner tree. SIAM J. Comput., 30(2):475-485, 2000. Google Scholar
  28. Sundar Vishwanathan. An approximation algorithm for the asymmetric travelling salesman problem with distances one and two. Inform. Process. Lett., 44(6):297-302, 1992. Google Scholar
  29. David P. Williamson. Analysis of the Held-Karp heuristic for the traveling salesman problem. Master’s thesis, MIT, 1990. 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