@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\})\$."
}