BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TN-95-24
       ENTRY:: October 09, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Approximation Algorithms for $k$-Delivery TSP
        TYPE:: Technical Note
      AUTHOR:: Chalasani, Prasad
      AUTHOR:: Motwani, Rajeev
        DATE:: August 1995
       PAGES:: 10
    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.
       NOTES:: [Adminitrivia V1/Prg/19951009]
         END:: STAN//CS-TN-95-24