TY - JOUR

T1 - Dial a ride from k-forest

AU - Gupta, Anupam

AU - Hajiaghayi, Mohammadtaghi

AU - Nagarajan, Viswanath

AU - Ravi, R.

PY - 2010/3/1

Y1 - 2010/3/1

N2 - The k-forest problem is a common generalization of both the k-MST and the dense-k-subgraph problems. Formally, given a metric space on n vertices V, with m demand pairs ⊆ V × V and a target k ≤ m, the goal is to find a minimum cost subgraph that connects at least k pairs. In this paper, we give an O(min{nlog k,k})-approximation algorithm for k-forest, improving on the previous best ratio of O(min {n2/3,m}log n) by Segev and Segev. We then apply our algsorithm for k-forest to obtain approximation algorithms for several Dial-a-Ride problems. The basic Dial-a-Ride problem is the following: given an n point metric space with m objects each with its own source and destination, and a vehicle capable of carrying at most k objects at any time, find the minimum length tour that uses this vehicle to move each object from its source to destination. We want that the tour be non-preemptive: that is, each object, once picked up at its source, is dropped only at its destination. We prove that an α-approximation algorithm for the k-forest problem implies an O(αlog2n)-approximation algorithm for Dial-a-Ride. Using our results for k-forest, we get an O(min{n,k}log2 n)-approximation algorithm for Dial-a-Ride. The only previous result known for Dial-a-Ride was an O(klog n)-approximation by Charikar and Raghavachari; our results give a different proof of a similar approximation guaranteein fact, when the vehicle capacity k is large, we give a slight improvement on their results. The reduction from Dial-a-Ride to the k-forest problem is fairly robust, and allows us to obtain approximation algorithms (with the same guarantee) for some interesting generalizations of Dial-a-Ride.

AB - The k-forest problem is a common generalization of both the k-MST and the dense-k-subgraph problems. Formally, given a metric space on n vertices V, with m demand pairs ⊆ V × V and a target k ≤ m, the goal is to find a minimum cost subgraph that connects at least k pairs. In this paper, we give an O(min{nlog k,k})-approximation algorithm for k-forest, improving on the previous best ratio of O(min {n2/3,m}log n) by Segev and Segev. We then apply our algsorithm for k-forest to obtain approximation algorithms for several Dial-a-Ride problems. The basic Dial-a-Ride problem is the following: given an n point metric space with m objects each with its own source and destination, and a vehicle capable of carrying at most k objects at any time, find the minimum length tour that uses this vehicle to move each object from its source to destination. We want that the tour be non-preemptive: that is, each object, once picked up at its source, is dropped only at its destination. We prove that an α-approximation algorithm for the k-forest problem implies an O(αlog2n)-approximation algorithm for Dial-a-Ride. Using our results for k-forest, we get an O(min{n,k}log2 n)-approximation algorithm for Dial-a-Ride. The only previous result known for Dial-a-Ride was an O(klog n)-approximation by Charikar and Raghavachari; our results give a different proof of a similar approximation guaranteein fact, when the vehicle capacity k is large, we give a slight improvement on their results. The reduction from Dial-a-Ride to the k-forest problem is fairly robust, and allows us to obtain approximation algorithms (with the same guarantee) for some interesting generalizations of Dial-a-Ride.

KW - Approximation algorithms

KW - Network design

KW - Vehicle routing

UR - http://www.scopus.com/inward/record.url?scp=77950856321&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77950856321&partnerID=8YFLogxK

U2 - 10.1145/1721837.1721857

DO - 10.1145/1721837.1721857

M3 - Article

AN - SCOPUS:77950856321

SN - 1549-6325

VL - 6

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 2

M1 - 41

ER -