Options
A 3/2-approximation for the metric many-visits path TSP
Citation Link: https://doi.org/10.15480/882.4137
Publikationstyp
Journal Article
Date Issued
2022
Sprache
English
Author(s)
Institut
TORE-DOI
TORE-URI
Volume
36
Issue
4
Start Page
2995
End Page
3030
Citation
SIAM Journal on Discrete Mathematics (2022)
Publisher DOI
Scopus ID
ArXiv ID
Publisher
Cornell University
In the Many-visits Path TSP, we are given a set of n cities along with their pairwise distances (or cost) 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 poly-logarithmic in the requests r(v).
Our algorithm can be seen as a far-reaching generalization of the 3/2-approximation algorithm for Path TSP by Zenklusen (SODA 2019), 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.
We tackle this problem by generalizing a fundamental result of Király, Lau and Singh (Combinatorica, 2012) on the Minimum Bounded Degree Matroid Basis problem, and devise such an algorithm for general 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.
We present a 3/2-approximation algorithm for the metric Many-visits Path TSP, that runs in time polynomial in n and poly-logarithmic in the requests r(v).
Our algorithm can be seen as a far-reaching generalization of the 3/2-approximation algorithm for Path TSP by Zenklusen (SODA 2019), 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.
We tackle this problem by generalizing a fundamental result of Király, Lau and Singh (Combinatorica, 2012) on the Minimum Bounded Degree Matroid Basis problem, and devise such an algorithm for general 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.
Subjects
traveling salesman problem
degree constraints
generalized polymatroids
DDC Class
510: Mathematik
Publication version
publishedVersion
Loading...
Name
2007.11389.pdf
Size
697.49 KB
Format
Adobe PDF