Abstract
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) |
|---|---|
| Pages (from-to) | 349-358 |
| Number of pages | 10 |
| Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |
| DOIs | |
| 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
- Software