Many-visits TSP revisited
Łukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, Magnus Wahlström · Journal of Computer and System Sciences · 2021
We study the Many-Visits Traveling Salesman 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⁎(5n). They also show a polynomial-space algorithm running in time O(16n+o(n)). In this work, we show three main results: A randomized polynomial-space algorithm running in time O⁎(2nD), where D is the maximum distance between two cities. By using standard methods, this results in a (1+ϵ)-approximation running in time O⁎(2nϵ−1). A tight analysis of Berger et al.'s exponential-space algorithm, resulting in an O⁎(4n) running time bound. A new polynomial-space algorithm, running in time O(7.88n).