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