Document Open Access Logo

Improving TSP Tours Using Dynamic Programming over Tree Decompositions

Authors Marek Cygan, Lukasz Kowalik, Arkadiusz Socala

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.30.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Marek Cygan
Lukasz Kowalik
Arkadiusz Socala

Cite AsGet BibTex

Marek Cygan, Lukasz Kowalik, and Arkadiusz Socala. Improving TSP Tours Using Dynamic Programming over Tree Decompositions. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ESA.2017.30

Abstract

Given a traveling salesman problem (TSP) tour H in graph G, a k-move is an operation which removes k edges from H, and adds k edges of G so that a new tour H' is formed. The popular k-opt heuristic for TSP finds a local optimum by starting from an arbitrary tour H and then improving it by a sequence of k-moves. Until 2016, the only known algorithm to find an improving k-move for a given tour was the naive solution in time O(n^k). At ICALP'16 de Berg, Buchin, Jansen and Woeginger showed an O(n^{floor(2/3k)+1})-time algorithm. We show an algorithm which runs in O(n^{(1/4 + epsilon_k)k}) time, where lim_{k -> infinity} epsilon_k = 0. It improves over the state of the art for every k >= 5. For the most practically relevant case k=5 we provide a slightly refined algorithm running in O(n^{3.4}) time. We also show that for the k=4 case, improving over the O(n^3)-time algorithm of de Berg et al. would be a major breakthrough: an O(n^{3 - epsilon})-time algorithm for any epsilon > 0 would imply an O(n^{3 - delta})-time algorithm for the All Pairs Shortest Paths problem, for some delta>0.
Keywords
  • TSP
  • treewidth
  • local search
  • XP algorithm
  • hardness in P

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 (JACM), 45(5):753-782, 1998. Google Scholar
  2. Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos. On exact algorithms for treewidth. ACM Trans. Algorithms, 9(1):12:1-12:23, 2012. Google Scholar
  3. Barun Chandra, Howard J. Karloff, and Craig A. 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, DTIC Document, 1976. Google Scholar
  5. Georges A Croes. A method for solving traveling-salesman problems. Operations research, 6(6):791-812, 1958. Google Scholar
  6. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  7. Marek Cygan, Lukasz Kowalik, and Arkadiusz Socala. Improving TSP tours using dynamic programming over tree decomposition. CoRR, abs/1703.05559, 2017. URL: http://arxiv.org/abs/1703.05559.
  8. Mark de Berg, Kevin Buchin, Bart M. P. Jansen, and Gerhard J. Woeginger. Fine-grained complexity analysis of two classic TSP variants. In ICALP, volume 55 of LIPIcs, pages 5:1-5:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  9. Fedor V. Fomin, Serge Gaspers, Saket Saurabh, and Alexey A. Stepanov. On two techniques of combining branching and treewidth. Algorithmica, 54(2):181-207, 2009. Google Scholar
  10. Fedor V. Fomin and Kjartan Høie. Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett., 97(5):191-196, 2006. Google Scholar
  11. Fedor V. Fomin and Yngve Villanger. Finding Induced Subgraphs via Minimal Triangulations. In Jean-Yves Marion and Thomas Schwentick, editors, 27th International Symposium on Theoretical Aspects of Computer Science, volume 5 of Leibniz International Proceedings in Informatics (LIPIcs), pages 383-394, Dagstuhl, Germany, 2010. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2470.
  12. Jiong Guo, Sepp Hartung, Rolf Niedermeier, and Ondrej Suchý. The parameterized complexity of local search for tsp, more refined. Algorithmica, 67(1):89-110, 2013. Google Scholar
  13. Michael Held and Richard M Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1):196-210, 1962. Google Scholar
  14. Keld Helsgaun. An effective implementation of the lin–kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1):106-130, 2000. URL: http://dx.doi.org/10.1016/S0377-2217(99)00284-2.
  15. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? J. Comput. Syst. Sci., 37(1):79-100, 1988. Google Scholar
  16. Richard M Karp. Dynamic programming meets the principle of inclusion and exclusion. Operations Research Letters, 1(2):49-51, 1982. Google Scholar
  17. Ton Kloks. Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer, 1994. Google Scholar
  18. Mark W. Krentel. On finding and verifying locally optimal solutions. SIAM J. Comput., 19(4):742-749, 1990. Google Scholar
  19. Marvin Künnemann and Bodo Manthey. Towards understanding the smoothed approximation ratio of the 2-opt heuristic. In ICALP (1), volume 9134 of Lecture Notes in Computer Science, pages 859-871. Springer, 2015. Google Scholar
  20. S. Lin and Brian W. Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2):498-516, 1973. URL: http://dx.doi.org/10.1287/opre.21.2.498.
  21. Shen Lin. Computer solutions of the traveling salesman problem. The Bell System Technical Journal, 44(10):2245-2269, 1965. Google Scholar
  22. Bodo Manthey and Rianne Veenstra. Smoothed analysis of the 2-opt heuristic for the TSP: polynomial bounds for gaussian noise. In ISAAC, volume 8283 of Lecture Notes in Computer Science, pages 579-589. Springer, 2013. Google Scholar
  23. Dániel Marx. Searching the k-change neighborhood for TSP is w[1]-hard. Oper. Res. Lett., 36(1):31-36, 2008. Google Scholar
  24. Manfred Padberg and Giovanni Rinaldi. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review, 33(1):60-100, 1991. URL: http://dx.doi.org/10.1137/1033004.
  25. 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
  26. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In FOCS, pages 645-654. IEEE Computer Society, 2010. 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