Given n identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to n target locations (slots) with a vehicle that can carry at most k pegs at a time. This problem is referred to as k-delivery TSP, and it is a generalization of the Traveling Salesman Problem. We give a 5-approximation algorithm for the problem of minimizing the total distance traveled by the vehicle. There are two kinds of transportation possible - one that could drop pegs at intermediate locations and pick them up later in the route for delivery (preemptive) and one that transports pegs to their targets directly (non-preemptive). In the former case, by exploiting the freedom to drop, one may be able to find a shorter delivery route. We construct a non-preemptive tour that is within a factor 5 of the optimal preemptive tour. In addition we show that the ratio of the distances traveled by an optimal non-preemptive tour versus a preemptive tour is bounded by 4.
|Original language||English (US)|
|Number of pages||10|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - 1998|
|Event||Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing - Dallas, TX, USA|
Duration: May 23 1998 → May 26 1998
ASJC Scopus subject areas