摘要：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â¿).
