Hardness of Preemptive Finite Capacity DialaRide 

Abstract  In the Finite Capacity DialaRide problem the input is a metric space, a set of objects, each specifying a source and a destination, and an integer kthe 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 DialaRide 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 