@CONFERENCE\{IMM2006-04685, author = "I. L. G{\o}rtz", title = "Hardness of Preemptive Finite Capacity Dial-a-Ride", year = "2006", month = "aug", keywords = "Hardness of approximation", booktitle = "Proc. 9th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems ({APPROX} 2006)", volume = "", series = "", editor = "Lecture Notes in Computer Science", publisher = "", organization = "", address = "", url = "http://www2.compute.dtu.dk/pubdb/pubs/4685-full.html", 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 \\$\\$\backslash\\$min\\$\backslash\\$\{O(\\$\backslash\\$log\^\{1/4-\\$\backslash\\$epsilon\}N),k\^\{1-\\$\backslash\\$varepsilon\}\\$\backslash\\$\}\\$-approximation algorithm for any \\$\\$\backslash\\$epsilon>0\\$ unless all problems in {NP} can be solved by randomized algorithms with expected running time \\$O(n\^\{loglog n\})\\$." }