A $(3/2+\epsilon )$-Approximation for Multiple TSP with a Variable Number of Depots

Max Deppert, Matthias Kaul, Matthias Mnich

One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is the {\sc Multiple TSP}: a set of $m\ge 1$ salespersons collectively traverses a set of $n$…