Tutte seminar - Zachary Friggstad

Multiple Traveling Salesmen in Asymmetric Metrics

Abstract:

Consider the problem of finding k paths of minimum total cost whose union covers all nodes in a asymmetric metric graph. When k=1, this is exactly the asymmetric traveling salesman path problem. I will present a bicriteria approximation algorithm that finds up to k + k/b paths with total cost at most O(b log n) times the optimum cost of using exactly k paths where b is an input parameter and n is the number of nodes. Setting b = 1 yields an O(log n) approximation using up to 2k paths and setting b = k+1 is a true O(k log n) approximation using exactly k paths. The approximation guarantee can be stated with respect to an LP relaxation of the problem. This approach generalizes to instances where the start and end nodes of the k paths are specified in advance provided that all start nodes are the same or all end nodes are the same. I will show that the most general case when all start and end nodes may be distinct cannot be approximated within any bounded ratio unless P = NP.