A PTAS for the Min-Max Euclidean Multiple TSP

Mary Monroe, David M. Mount

We present a polynomial-time approximation scheme (PTAS) for the min-max multiple TSP problem in Euclidean space, where multiple traveling salesmen are tasked with visiting a set o…