Advertisement
Published in:
2006 | OriginalPaper | Chapter
Hardness of Preemptive Finite Capacity Dial-a-Ride
Author : Inge Li Gørtz
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In the
Finite Capacity Dial-a-Ride problem
the input is a metric space, a set of objects {
d
i
}, each specifying a source
s
i
and a destination
t
i
, 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 has no min {
O
(log
$^{\rm 1/4-{\it \epsilon}}$
N
),
k
1 − ε
}-approximation algorithm for any
ε
> 0 unless all problems in NP can be solved by randomized algorithms with expected running time
O
(
n
polylog
n
).