A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of Depots
share
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 function is the sum of all tour lengths. When all m tours start from a single common depot v_0, then the metric Multiple TSP can be approximated equally well as the standard metric TSP, as shown by Frieze (1983). The 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 Multiple TSP running in time n^Θ(d) and reducing the problem to approximating 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/ε)^𝒪(dlog d)· n^𝒪(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^𝒪(1).ithm for metric Multiple TSP with run time n^Θ(d), which reduces the problem to approximating metric TSP.
READ FULL TEXT