SPEAKER: Viswanath Nagarajan
TIME: Wednesday 12-1pm, October 11, 2006
PLACE: NSH 1507
TITLE: Approximating the Dial-a-Ride problem
ABSTRACT:
The Dial-a-Ride problem is the following: given an $n$ vertex metric space,
$m$ objects each specified by a source-destination pair, and a vehicle of
capacity $k$, find the minimum length tour that moves each object from its
source to destination such that there are at most $k$ objects in the vehicle
at any point in the tour. The tour is said to be non-preemptive if each
object, once picked up at its source is dropped only at its destination. The
tour is said to be preemptive if each object can be dropped at intermediate
vertices before being delivered at its destination.
We give an approximation algorithm for the non-preemptive Dial-a-Ride problem
which achieves a guarantee of $\tilde{O}(min{\sqrt{n},\sqrt{k}})$. When the
capacity $k$ is large, this is an improvement over the previous best
approximation ratio of $\tilde{O}(\sqrt{k})$ due to Charikar & Raghavachari
'98. We also show that there is always a tour that preempts each object at
most once, and has a cost $O(\log^2 n)$ times the optimal (many) preemptive
tour.
Joint work with Anupam Gupta, M.T. Hajiaghayi, and R. Ravi