Options
A (3/2 + ε)-Approximation for multiple TSP with a variable number of depots
Citation Link: https://doi.org/10.15480/882.8445
Publikationstyp
Conference Paper
Date Issued
2023-08
Sprache
English
TORE-DOI
Citation
European Symposium on Algorithms (ESA 2023)
Contribution to Conference
Publisher DOI
Scopus ID
One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is the Multiple TSP: a set of m ≥ 1 salespersons collectively traverses a set of n cities by m non-trivial
tours, to minimize the total length of their tours. This problem can also be considered to be a variant of Uncapacitated Vehicle Routing, where the objective is to minimize the sum of all tour lengths. When all m tours start from and end at a single common depot v0, then the metric Multiple TSP can be approximated equally well as the standard metric TSP, as shown by Frieze (1983).
The metric Multiple TSP becomes significantly harder to approximate when there is a set D of d ≥ 1 depots that form the starting and end points of the m tours. For this case, only a
(2 − 1/d)-approximation in polynomial time is known, as well as a 3/2-approximation for constant d which requires a prohibitive run time of n^Θ(d) (Xu and Rodrigues, INFORMS J. Comput., 2015). A recent work of Traub, Vygen and Zenklusen (STOC 2020) gives another approximation algorithm for metric Multiple TSP with run time n^Θ(d), which reduces the problem to approximating metric TSP.
In this paper we overcome the n^Θ(d) time barrier: we give the first efficient approximation algorithm for Multiple TSP with a variable number d of depots that yields a better-than-2 approximation. Our algorithm runs in time (1/ε)^O(d log d)· n^O(1), and produces a (3/2 + ε)-approximation with constant probability. For the graphic case, we obtain a deterministic 3/2-approximation in time 2^d· n^O(1).
tours, to minimize the total length of their tours. This problem can also be considered to be a variant of Uncapacitated Vehicle Routing, where the objective is to minimize the sum of all tour lengths. When all m tours start from and end at a single common depot v0, then the metric Multiple TSP can be approximated equally well as the standard metric TSP, as shown by Frieze (1983).
The metric Multiple TSP becomes significantly harder to approximate when there is a set D of d ≥ 1 depots that form the starting and end points of the m tours. For this case, only a
(2 − 1/d)-approximation in polynomial time is known, as well as a 3/2-approximation for constant d which requires a prohibitive run time of n^Θ(d) (Xu and Rodrigues, INFORMS J. Comput., 2015). A recent work of Traub, Vygen and Zenklusen (STOC 2020) gives another approximation algorithm for metric Multiple TSP with run time n^Θ(d), which reduces the problem to approximating metric TSP.
In this paper we overcome the n^Θ(d) time barrier: we give the first efficient approximation algorithm for Multiple TSP with a variable number d of depots that yields a better-than-2 approximation. Our algorithm runs in time (1/ε)^O(d log d)· n^O(1), and produces a (3/2 + ε)-approximation with constant probability. For the graphic case, we obtain a deterministic 3/2-approximation in time 2^d· n^O(1).
Subjects
multiple TSP
rural postperson problem
Traveling salesperson problem
vehicle routing
DDC Class
510: Mathematics
600: Technology
Publication version
publishedVersion
Loading...
Name
LIPIcs-ESA-2023-39.pdf
Size
849.91 KB
Format
Adobe PDF