Institute of Transportation Studies at UC Berkeley

Though 2-approximation algorithms are available for several Multiple Depot Travelling Salesman Problems (TSPs)and Hamiltonian Path Problems (HPPs), there are no algorithms in the literature for any multiple depot variant of TSP or HPP that has an approximation ratio better than 2. This paper addresses one variant of the Multiple Depot HPP and provides the first 5/3-approximation algorithm for the same when the costs are symmetric and satisfy triangle inequality.