Time- and space-optimal algorithm for the many-visits TSP

DOI10.1145/3382038MaRDI QIDQ4987455zbMATH OpenOpenAlexFDO

Authors André Berger, László Kozma, Matthias Mnich, Roland Vincze

Publication date 3 May 2021

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.06361, http://hdl.handle.net/11420/4450

zbMATH Keywords

high-multiplicity schedulingspanning treesTSP

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Abstract: 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}logsu{m}_c{k}_c)$ and requires $n^{Theta(n)}$ space. An interesting feature of the Cosmadakis-Papadimitriou algorithm is its emph{logarithmic} dependence on the total length $su{m}_c{k}_c$ of the tour, allowing the algorithm to handle instances with very long tours. The emph{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 paper we improve upon the Cosmadakis-Papadimitriou algorithm, giving an MV-TSP algorithm that runs in time $2^{O(n)}$, i.e. emph{single-exponential} in the number of cities, using emph{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.

Recommendations

• A time- and space-optimal algorithm for the many-visits TSP
• Many-visits TSP revisited
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• scientific article; zbMATH DE number 4053381
• Approximating asymmetric TSP in exponential time

Cited in

(7)

• Many-visits TSP revisited
• On the high multiplicity traveling salesman problem
• On the parameterized complexity of the connected flow and many visits TSP problem
• scientific article; zbMATH DE number 4053381 (Why is no real title available?)
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• A time- and space-optimal algorithm for the many-visits TSP
• Preprocessing complexity for some graph problems parameterized by structural parameters

This page was built for publication: Time- and space-optimal algorithm for the many-visits TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4987455)