The k-forest problem is a common generalization of both the k-MST and the dense- @math -subgraph problems. Formally, given a metric space on @math vertices @math , with @math demand pairs @math and a target'' @math , the goal is to find a minimum cost subgraph that connects at least @math demand pairs. In this paper, we give an @math -approximation algorithm for @math -forest, improving on the previous best ratio of @math by Segev & Segev. 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 @math point metric space with @math objects each with its own source and destination, and a vehicle capable of carrying at most @math 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 @math -approximation algorithm for the @math -forest problem implies an @math -approximation algorithm for Dial-a-Ride. Using our results for @math -forest, we get an @math - approximation algorithm for Dial-a-Ride. The only previous result known for Dial-a-Ride was an @math -approximation by Charikar & Raghavachari; our results give a different proof of a similar approximation guarantee--in fact, when the vehicle capacity @math is large, we give a slight improvement on their results.
We present a polynomial time 2-approximation algorithm for the problem of finding the minimum tree that spans at least k vertices. Our result also leads to a 2-approximation algorithm for finding the minimum tour that visits k vertices and to a 3-approximation algorithm for the problem of finding the maximum number of vertices that can be spanned by a tree of length at most a given bound. In this paper we study the prize-collecting version of the Generalized Steiner Tree problem. To the best of our knowledge, there is no general combinatorial technique in approximation algorithms developed to study the prize-collecting versions of various problems. These problems are studied on a case by case basis by [5] by applying an LP-rounding technique which is not a combinatorial approach. The main contribution of this paper is to introduce a general combinatorial approach towards solving these problems through novel primal-dual schema (without any need to solve an LP). We fuse the primal-dual schema with Farkas lemma to obtain a combinatorial 3-approximation algorithm for the Prize-Collecting Generalized Steiner Tree problem. Our work also inspires a combinatorial algorithm [19] for solving a special case of Kelly's problem [22] of pricing edges.We also consider the k-forest problem, a generalization of k-MST and k-Steiner tree, and we show that in spite of these problems for which there are constant factor approximation algorithms, the k-forest problem is much harder to approximate. In particular, obtaining an approximation factor better than O(n1 6-e) for k-forest requires substantially new ideas including improving the approximation factor O(n1 3-e) for the notorious densest k-subgraph problem. We note that k-forest and prize-collecting version of Generalized Steiner Tree are closely related to each other, since the latter is the Lagrangian relaxation of the former. We consider the k-traveling repairmen problem, also known as the minimum latency problem, to multiple repairmen. We give a polynomial-time 8.497α-approximation algorithm for this generalization, where α denotes the best achievable approximation factor for the problem of finding the least-cost rooted tree spanning i vertices of a metric. For the latter problem, a (2 p e)-approximation is known. Our results can be compared with the best-known approximation algorithm using similar techniques for the case k e 1, which is 3.59α. Moreover, recent work of [2003] shows how to remove the factor of α, thus improving all of these results by that factor. We are aware of no previous work on the approximability of the present problem. In addition, we give a simple proof of the 3.59α-approximation result that can be more easily extended to the case of multiple repairmen, and may be of independent interest.