2026-08-11T08:33:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18692 2024-03-06T11:02:28Z ddc:004 open_access

A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of Depots Deppert, Max Kaul, Matthias Mnich, Matthias Traveling salesperson problem rural postperson problem multiple TSP vehicle routing 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 v₀, 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(dlog 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Max Deppert and Matthias Kaul and Matthias Mnich 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.39 urn:nbn:de:0030-drops-186925 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.39 eng https://creativecommons.org/licenses/by/4.0/legalcode