CS Forum: Matthias Mnich, University of Bonn "A time- and space-optimal algorithm for the many-visits TSP"
A time- and space-optimal algorithm for the many-visits TSP
Dr Matthias Mnich
University of Bonn
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 n^O(n)+O(n^3 log∑_c k_c) and requires n^O(n) space. An interesting feature of the Cosmadakis-Papadimitriou algorithm is its \emph dependence on the total length ∑_c k_c of the tour, allowing the algorithm to handle instances with very long tours, beyond what is tractable in the standard TSP setting. However, the 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 2^O(n), i.e. single-exponential in the number of cities, with polynomial space. 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.
(appears at SODA 2019; joint work with André Berger, László Kozma und Roland Vincze)
CS forum is a seminar series arranged at the CS department. The talks are intended for presentations of postdoctoral level researchers and professors, both for visiting and CS-department-based researchers.