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