2026-07-22T06:37:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12932 2024-03-06T10:51:07Z ddc:004 open_access

Many Visits TSP Revisited Kowalik, Łukasz Li, Shaohua Nadara, Wojciech Smulewicz, Marcin Wahlström, Magnus many visits traveling salesman problem exponential algorithm 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ⁿ). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Łukasz Kowalik and Shaohua Li and Wojciech Nadara and Marcin Smulewicz and Magnus Wahlström 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.66 urn:nbn:de:0030-drops-129329 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.66 eng https://creativecommons.org/licenses/by/3.0/legalcode