In the Many-visits Path TSP, we are given a set of $n$ cities along with their pairwise distances (or costs) $c(uv)$, and moreover each city $v$ comes with an associated positive integer request $r(v)$. The goal is to find a minimum-cost path, starting at city $s$ and ending at city $t$, that visits each city $v$ exactly $r(v)$ times. We present a $3/2$-approximation algorithm for the metric Many-visits Path TSP that runs in time polynomial in $n$ and polylogarithmic in the requests $r(v)$. Our algorithm can be seen as a generalization of the $3/2$-approximation algorithm for Path TSP by Zenklusen [ Proceedings of SODA, 2019, pp. 1539--1549], which answered a long-standing open problem by providing an efficient algorithm which matches the approximation guarantee of Christofides' algorithm from 1976 for metric TSP. One of the key components of our approach is a polynomial-time algorithm to compute a connected, degree-bounded multigraph of minimum cost in an undirected graph with edge costs. We tackle this problem by generalizing a fundamental result of Király, Lau, and Singh [ Combinatorica, 32 (2012), pp. 705--720] on the Minimum Bounded Degree Matroid Basis problem, and devise such an algorithm for generalized polymatroids, even allowing element multiplicities. Our result directly yields a $3/2$-approximation to the metric Many-visits TSP, as well as a $3/2$-approximation for the problem of scheduling classes of jobs with sequence-dependent setup times on a single machine so as to minimize the makespan.

The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number k c of times. Travel costs may be asymmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families. The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984). It runs in time n O(n) + O(n 3 log ∑ c k c ) and requires n ᶿ(n) space. An interesting feature of the Cosmadakis-Papadimitriou algorithm is its logarithmic dependence on the total length ∑ c k c of the tour, allowing the algorithm to handle instances with very long tours. The superexponential dependence on the number of cities in both the time and space complexity, however, renders the algorithm impractical for all but the narrowest range of this parameter. In this article, we improve upon the Cosmadakis-Papadimitriou algorithm, giving an MV-TSP algorithm that runs in time 2 O(n) , i.e., single-exponential in the number of cities, using polynomial space. The space requirement of our algorithm is (essentially) the size of the output, and assuming the Exponential-Time Hypothesis (ETH), the problem cannot be solved in time 2 o(n) . Our algorithm is deterministic, and arguably both simpler and easier to analyze than the original approach of Cosmadakis and Papadimitriou. It involves an optimization over directed spanning trees and a recursive, centroid-based decomposition of trees.

The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number kc of times. Travel costs may be asymmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families. The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984). It runs in time nO(n) + O(n3 log Σc kc) and requires nO(n) space. The interesting feature of the Cosmadakis-Papadimitriou algorithm is its logarithmic dependence on the total length Σc kc of the tour, allowing the algorithm to handle instances with very long tours, beyond what is tractable in the standard TSP setting. However, its superexponential dependence on the number of cities in both its time and space complexity renders the algorithm impractical for all but the narrowest range of this parameter. In this paper we significantly improve on the Cosmadakis-Papadimitriou algorithm, giving an MV-TSP algorithm that runs in time 2O(n), i.e. single-exponential in the number of cities, with polynomial space. The space requirement of our algorithm is (essentially) the size of the output, and assuming the Exponential-time Hypothesis (ETH), the time requirement is optimal. Our algorithm is deterministic, and arguably both simpler and easier to analyse than the original approach of Cosmadakis and Papadimitriou. It involves an optimization over directed spanning trees and a recursive, centroid-based decomposition of trees.