Computer Science – Data Structures and Algorithms
Scientific paper
2011-02-26
Computer Science
Data Structures and Algorithms
22 pages, 1 figure. Preliminary version appeared in ESA 2009
Scientific paper
Dial a ride problems consist of a metric space (denoting travel time between vertices) and a set of m objects represented as source-destination pairs, where each object requires to be moved from its source to destination vertex. We consider the multi-vehicle Dial a ride problem, with each vehicle having capacity k and its own depot-vertex, where the objective is to minimize the maximum completion time (makespan) of the vehicles. We study the "preemptive" version of the problem, where an object may be left at intermediate vertices and transported by more than one vehicle, while being moved from source to destination. Our main results are an O(log^3 n)-approximation algorithm for preemptive multi-vehicle Dial a ride, and an improved O(log t)-approximation for its special case when there is no capacity constraint. We also show that the approximation ratios improve by a log-factor when the underlying metric is induced by a fixed-minor-free graph.
Goertz Inge Li
Nagarajan Viswanath
Ravi R.
No associations
LandOfFree
Minimum Makespan Multi-vehicle Dial-a-Ride does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Minimum Makespan Multi-vehicle Dial-a-Ride, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Makespan Multi-vehicle Dial-a-Ride will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-53677