A Submodular Optimization Approach to the Metric Traveling Salesman Problem with Neighborhoods

The Traveling Salesman Problem with Neighborhoods (TSPN) is a generalization of the classic Traveling Salesman Problem that consists of finding a minimum-length path that reaches a set of regions and then returns to the origin. We consider the metric TSPN, in which the length function is a metric, and develop two approximation algorithms. First, we exploit the connection between the TSP and minimum spanning trees to develop a submodular optimization approach, in which we show that the TSPN is equivalent to maximizing a submodular function with a spanning tree constraint. We prove that the resulting tour is within a factor of 4 of the optimum. Second, we develop a convex relaxation of the problem that gives a lower bound on the optimal tour length, as well as a straightforward rounding procedure that gives an alternative heuristic for TSPN. We evaluate our approaches through numerical study.