Document Open Access Logo

Many Visits TSP Revisited

Authors Łukasz Kowalik , Shaohua Li, Wojciech Nadara, Marcin Smulewicz, Magnus Wahlström

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.66.pdf
  • Filesize: 0.95 MB
  • 22 pages

Document Identifiers

Author Details

Łukasz Kowalik
  • Institute of Informatics, University of Warsaw, Poland
Shaohua Li
  • Institute of Informatics, University of Warsaw, Poland
Wojciech Nadara
  • Institute of Informatics, University of Warsaw, Poland
Marcin Smulewicz
  • Institute of Informatics, University of Warsaw, Poland
Magnus Wahlström
  • Royal Holloway, University of London, UK

Funding

This workshop was supported by a project that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement No 714704 (PI: Marcin Pilipczuk).
  • Kowalik, Łukasz: Supported by ERC Starting Grant TOTAL (Grant Agreement No 677651).
  • Li, Shaohua: Supported by ERC Starting Grant CUTACOMBS (Grant Agreement No 714704).
  • Nadara, Wojciech: Supported by ERC Starting Grant CUTACOMBS (Grant Agreement No 714704).
  • Smulewicz, Marcin: Supported by ERC Starting Grant TOTAL (Grant Agreement No 677651).

Acknowledgements

The research leading to the results presented in this paper was partially carried out during the Parameterized Algorithms Retreat of the University of Warsaw, PARUW 2020, held in Krynica-Zdrój in February 2020.

Cite As Get BibTex

Łukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, and Magnus Wahlström. Many Visits TSP Revisited. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 66:1-66:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.66

Abstract

We study the Many Visits TSP problem, where given a number k(v) for each of n cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that visits each city v exactly k(v) times. The currently fastest algorithm is due to Berger, Kozma, Mnich and Vincze [SODA 2019, TALG 2020] and runs in time and space O*(5ⁿ). They also show a polynomial space algorithm running in time O(16^{n+o(n)}). In this work, we show three main results:  
- A randomized polynomial space algorithm in time O*(2^n D), where D is the maximum distance between two cities. By using standard methods, this results in a (1+ε)-approximation in time O*(2ⁿε^{-1}). Improving the constant 2 in these results would be a major breakthrough, as it would result in improving the O*(2ⁿ)-time algorithm for Directed Hamiltonian Cycle, which is a 50 years old open problem. 
- A tight analysis of Berger et al.’s exponential space algorithm, resulting in an O*(4ⁿ) running time bound. 
- A new polynomial space algorithm, running in time O(7.88ⁿ).

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • many visits traveling salesman problem
  • exponential algorithm

Metrics

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

References

  1. Richard Bellman. Dynamic programming treatment of the travelling salesman problem. J. ACM, 9(1):61–63, January 1962. URL: https://doi.org/10.1145/321105.321111.
  2. André Berger, László Kozma, Matthias Mnich, and Roland Vincze. Time- and space-optimal algorithms for the many-visits TSP. CoRR, abs/1804.06361, 2018. URL: http://arxiv.org/abs/1804.06361.
  3. André Berger, László Kozma, Matthias Mnich, and Roland Vincze. A time- and space-optimal algorithm for the many-visits TSP. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1770-1782. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.106.
  4. Andreas Björklund, Petteri Kaski, and Ioannis Koutis. Directed Hamiltonicity and out-branchings via generalized Laplacians. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 91:1-91:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.91.
  5. Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. Fast witness extraction using a decision oracle. In ESA, volume 8737 of Lecture Notes in Computer Science, pages 149-160. Springer, 2014. Google Scholar
  6. Nadia Brauner, Yves Crama, Alexander Grigoriev, and Joris Van de Klundert. A framework for the complexity of high-multiplicity scheduling problems. J. Comb. Optim., 9:313-323, May 2005. URL: https://doi.org/10.1007/s10878-005-1414-7.
  7. Stavros S. Cosmadakis and Christos H. Papadimitriou. The traveling salesman problem with many visits to few cities. SIAM J. Comput., 13(1):99-108, 1984. Google Scholar
  8. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems as hard as CNF-SAT. ACM Trans. Algorithms, 12(3), May 2016. URL: https://doi.org/10.1145/2925416.
  9. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast Hamiltonicity checking via bases of perfect matchings. J. ACM, 65(3), March 2018. URL: https://doi.org/10.1145/3148227.
  10. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In FOCS, pages 150-159. IEEE Computer Society, 2011. Google Scholar
  11. R. A. DeMillo and R. J. Lipton. A probabilistic remark on algebraic program testing. Inf. Process. Lett., 7:193-195, 1978. Google Scholar
  12. Hamilton Emmons and Kamlesh Mathur. Lot sizing in a no-wait flow shop. Operations Research Letters - ORL, 17:159-164, May 1995. URL: https://doi.org/10.1016/0167-6377(95)00008-8.
  13. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010. Google Scholar
  14. Alexander Grigoriev and Joris Van de Klundert. On the high multiplicity traveling salesman problem. Discrete Optimization, 3:50-62, March 2006. URL: https://doi.org/10.1016/j.disopt.2005.11.002.
  15. Yuri Gurevich and Saharon Shelah. Expected computation time for Hamiltonian path problem. SIAM J. Comput., 16(3):486–502, June 1987. URL: https://doi.org/10.1137/0216034.
  16. Michael Held and Richard M. Karp. A dynamic programming approach to sequencing problems. In Proceedings of the 1961 16th ACM National Meeting, ACM ’61, page 71.201–71.204, New York, NY, USA, 1961. Association for Computing Machinery. URL: https://doi.org/10.1145/800029.808532.
  17. Dorit S. Hochbaum and Ron Shamir. Strongly polynomial algorithms for the high multiplicity scheduling problem. Oper. Res., 39:648-653, 1991. Google Scholar
  18. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  19. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  20. László Kozma and Tobias Mömke. Maximum scatter TSP in doubling metrics. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, page 143–153, USA, 2017. Society for Industrial and Applied Mathematics. Google Scholar
  21. Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. In Algorithms - ESA 2010, volume 64, pages 549-560, September 2010. URL: https://doi.org/10.1007/978-3-642-15775-2_47.
  22. László Lovász. On determinants, matchings and random algorithms. In FCT, volume 79, pages 565-574, January 1979. Google Scholar
  23. James B. Orlin. A faster strongly polynomial minimum cost flow algorithm. Oper. Res., 41(2):338-350, 1993. URL: https://doi.org/10.1287/opre.41.2.338.
  24. Harilaos N. Psaraftis. A dynamic programming approach for sequencing groups of identical jobs. Operations Research, 28(6):1347-1359, 1980. Google Scholar
  25. Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, 1980. URL: https://doi.org/10.1145/322217.322225.
  26. W. T. Tutte. The factorization of linear graphs. Journal of the London Mathematical Society, s1-22(2):107-111, April 1947. URL: https://doi.org/10.1112/jlms/s1-22.2.107.
  27. Jack A. A. van der Veen and Shuzhong Zhang. Low-complexity algorithms for sequencing jobs with a fixed number of job-classes. Comput. Oper. Res., 23(11):1059–1067, November 1996. URL: https://doi.org/10.1016/0305-0548(96)00016-0.
  28. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Proc. International Symposium on Symbolic and Algebraic Computation, volume 72 of LNCS, pages 216-226, 1979. 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