Document Open Access Logo

Graphic TSP in Cubic Graphs

Authors Zdenek Dvorák, Daniel Král, Bojan Mohar

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.27.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Zdenek Dvorák
Daniel Král
Bojan Mohar

Cite As Get BibTex

Zdenek Dvorák, Daniel Král, and Bojan Mohar. Graphic TSP in Cubic Graphs. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.27

Abstract

We present a polynomial-time 9/7-approximation algorithm for the graphic TSP for cubic graphs, which improves the previously best approximation factor of 1.3 for 2-connected cubic graphs and drops the requirement of 2-connectivity at the same time. To design our algorithm, we prove that every simple 2-connected cubic n-vertex graph contains a spanning closed walk of length at most 9n/7-1, and that such a walk can be found in polynomial time.

Subject Classification

Keywords
  • Graphic TSP
  • approximation algorithms
  • cubic graphs

Metrics

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

References

  1. Nishita Aggarwal, Naveen Garg, and Swati Gupta. A 4/3-approximation for TSP on cubic 3-edge-connected graphs. arXiv e-prints, 1101.5586, 2011. Google Scholar
  2. Sylvia Boyd, René Sitters, Suzanne van der Ster, and Leen Stougie. The traveling salesman problem on cubic and subcubic graphs. Mathematical Programming, 144(1-2):227-245, 2014. Google Scholar
  3. Barbora Candráková and Robert Lukot'ka. Cubic TSP - a 1.3-approximation. arXiv e-prints, 1506.06369, 2015. Google Scholar
  4. Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, DTIC Document, 1976. Google Scholar
  5. José Correa, Omar Larré, and José A Soto. TSP tours in cubic graphs: beyond 4/3. SIAM Journal on Discrete Mathematics, 29(2):915-939, 2015. Google Scholar
  6. Jack Edmonds. Maximum matching and a polyhedron with 0, l-vertices. J. Res. Nat. Bur. Standards B, 69(1965):125-130, 1965. Google Scholar
  7. David Gamarnik, Moshe Lewenstein, and Maxim Sviridenko. An improved upper bound for the TSP in cubic 3-edge-connected graph. Operations Research Letters, 33:467-474, 2005. Google Scholar
  8. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science &Business Media, 2012. Google Scholar
  9. Jeremy Karp and R Ravi. A 9/7-approximation algorithm for graphic TSP in cubic bipartite graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), volume 28 of Leibniz International Proceedings in Informatics (LIPIcs), pages 284-296. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.284.
  10. Marek Karpinski, Michael Lampis, and Richard Schmied. New inapproximability bounds for TSP. Journal of Computer and System Sciences, 81:1665-1677, 2015. Google Scholar
  11. Marek Karpinski and Richard Schmied. Approximation hardness of graphic TSP on cubic graphs. RAIRO Operations Research, 49:651-668, 2015. Google Scholar
  12. M. Lampis. Improved inapproximability for TSP. Lecture Notes in Computer Science, 7408:243-253, 2013. Google Scholar
  13. Jan Mazák and Robert Lukot'ka. Simple cubic graphs with no short travelling salesman tour, 2016. Manuscript. Google Scholar
  14. Tobias Mömke and Ola Svensson. Approximating graphic TSP by matchings. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 560-569. IEEE, 2011. Google Scholar
  15. Marcin Mucha. 13/9-approximation for graphic TSP. Theory of Computing Systems, 55:640-657, 2014. Google Scholar
  16. Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. A randomized rounding approach to the traveling salesman problem. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 550-559. IEEE, 2011. Google Scholar
  17. Manfred W. Padberg and M. R. Rao. Odd minimum cut-sets and b-matchings. Mathematics of Operations Research, 7(1):67-80, 1982. Google Scholar
  18. Christos H. Papadimitriou and Santosh Vempala. On the approximability of the traveling salesman problem. Combinatorica, 26:101-120, 2006. Google Scholar
  19. 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:597-629, 2014. Google Scholar
  20. Anke van Zuylen. Improved approximations for cubic and cubic bipartite TSP. In Integer Programming and Combinatorial Optimization (IPCO), volume 9682 of Lecture Notes in Computer Science, pages 250-261. Springer, 2016. 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 About DROPS Imprint Privacy Contact