## Abstract

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 demand pairs. In this paper, we give an O(min{√n, √k})-approximation algorithm for k-forest, improving on the previous best ratio of O(min{n^{2/3}, √m}log n) by Segev and Segev [20]. We then apply our algorithm 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 prove that an α-approximation algorithm for the k-forest problem implies an O(α·log^{2} n)-approximation algorithm for Dial-a-Ride. Using our results for k-forest, we get an O(min{√n, √k} ·log^{2} n)-approximation algorithm for Dial-a-Ride. The only previous result known for Dial-a-Ride was an O(√k log n)-approximation by Charikar and Raghavachari [5]; our results give a different proof of a similar approximation guarantee-in 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 the following generalizations: (i) Non-uniform Dial-a-Ride, where the cost of traversing each edge is an arbitrary non-decreasing function of the number of objects in the vehicle; and (ii) Weighted Dial-a-Ride, where demands are allowed to have different weights. The reduction is essential, as it is unclear how to extend the techniques of Charikar and Raghavachari to these Dial-a-Ride generalizations.

Original language | English (US) |
---|---|

Title of host publication | Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings |

Publisher | Springer Verlag |

Pages | 241-252 |

Number of pages | 12 |

ISBN (Print) | 9783540755197 |

DOIs | |

State | Published - 2007 |

Event | 15th Annual European Symposium on Algorithms, ESA 2007 - Eilat, Israel Duration: Oct 8 2007 → Oct 10 2007 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4698 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 15th Annual European Symposium on Algorithms, ESA 2007 |
---|---|

Country/Territory | Israel |

City | Eilat |

Period | 10/8/07 → 10/10/07 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science