Answers are grounded in this paper and cite their sources.
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).
No takes yet. Share an insight, caveat, or question.
Kowalik et al. (2021) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: