Hardness of Preemptive Finite Capacity Dial-a-Ride |
|
| Abstract | In the Finite Capacity Dial-a-Ride problem the input is a metric space, a set of objects, each specifying a source and a destination, and an integer k---the capacity of the vehicle used for making the deliveries. The goal is to compute a shortest tour for the vehicle in which all objects can be delivered from their sources to their destinations while ensuring that the vehicle carries at most k objects at any point in time.
In the preemptive version an object may be dropped at intermediate locations and picked up later and delivered.
Let N be the number of nodes in the input graph. Charikar and Raghavachari [FOCS '98] gave a min{O(log N),O(k)}-approximation algorithm for the preemptive version of the problem. In this paper we show that the preemptive Finite Capacity Dial-a-Ride problem has no $\min\{O(\log^{1/4-\epsilon}N),k^{1-\varepsilon}\}$-approximation algorithm for any $\epsilon>0$ unless all problems in NP can be solved by randomized algorithms with expected running time $O(n^{loglog n})$. |
| Keywords | Hardness of approximation |
| Type | Conference paper [With referee] |
| Conference | Proc. 9th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2006) |
| Editors | Lecture Notes in Computer Science |
| Year | 2006 Month August |
| BibTeX data | [bibtex] |
| IMM Group(s) | Computer Science & Engineering |