Report Number: CS-TN-95-24
Institution: Stanford University, Department of Computer Science
Title: Approximation Algorithms for $k$-Delivery TSP
Author: Chalasani, Prasad
Author: Motwani, Rajeev
Date: August 1995
Abstract: We provide O(1) approximation algorithms for the following NP-hard problem called k-Delivery TSP: We have at our disposal a truck of capacity k, and there are n depots and n customers at various locations in some metric space, and exactly one item (all of which are identical) at each depot. We want to find an optimal tour using the truck to deliver one item to each customer. Our algorithms run in time polynomial in both n and k. The 1-Delivery problem is one of finding an optimal tour that alternately visits depots and customers. For this case we use matroid intersection to show a polynomial-time 2-approximation algorithm, improving upon a factor 2.5 algorithm of Anily and Hassin. Using this approximation combined with certain lower bounding arguments we show a factor 11.5 approximation to the optimal k-Delivery tour. For the infinite k case we show a factor 2 approximation.
http://i.stanford.edu/pub/cstr/reports/cs/tn/95/24/CS-TN-95-24.pdf