Please use this identifier to cite or link to this item:
Fulltext available Open Access
Publisher DOI: 10.1137/1.9781611975482.106
Title: A time- and space-optimal algorithm for the many-visits TSP
Language: English
Authors: Berger, André 
Kozma, László 
Mnich, Matthias  
Vincze, Roland  
Issue Date: 2019
Publisher: Society for Industrial and Applied Mathematics
Source: 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)
Abstract (english): 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 \sum_c k_c ) and requires n^{O(n)} space. The interesting feature of the Cosmadakis-Papadimitriou algorithm is its \emph{logarithmic} dependence on the total length \sum_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, 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 2^{O(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.
Conference: Symposium on Discrete Algorithms, SODA 2019 
DOI: 10.15480/882.2590
Institute: Algorithmen und Komplexität E-11 
Type: InProceedings (Aufsatz / Paper einer Konferenz etc.)
License: In Copyright In Copyright
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
paper 132.pdf438,01 kBAdobe PDFThumbnail
Show full item record

Page view(s)

Last Week
Last month
checked on Nov 28, 2020


checked on Nov 28, 2020

Google ScholarTM


Note about this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.