Balanced TSP partitioning

Abstract

The traveling salesman problem (TSP) famously asks for a shortest tour that a salesperson can take to visit a given set of cities in any order. In this paper, we ask how much faster $k\ge 2$ salespeople can visit the cities if they divide the task among themselves. We show that, in the two-dimensional Euclidean setting, two salespeople can always achieve a speedup of at least $\frac{1}{2}+\frac{1}{\ddot{I}}€\approx 0.818$, for any given input, and there are inputs where they cannot do better. We also give (non-matching) upper and lower bounds for $k\ge 3$.