Improved approximation algorithm for steiner k-forest with nearly uniform weights

In the Steiner k-Forest problem, we are given an edge weighted graph, a collection D of node pairs, and an integer k . |D|. The goal is to find amin-weight subgraph that connects at least k pairs. The best known ratio for this problem is min{O( �ã n), O( �ã k)} [Gupta et al. 2010]. In Gupta et al. [2010], it is also shown that ratio ƒÏ for Steiner k-Forest implies ratio O(ƒÏ �E log2 n) for the related Dial-a-Ride problem. The only other algorithm known for Dial-a-Ride, besides the one resulting from Gupta et al. [2010], has ratio O( �ã n) [Charikar and Raghavachari 1998]. We obtain approximation ratio n0.448 for Steiner k-Forest and Dial-a-Ride with unit weights, breaking the O( �ã n) approximation barrier for this natural case. We also show that if the maximum edge-weight is O(nε), then one can achieve ratio O(n(1+ε)�E0.448), which is less than �ã n if ε is small enough. The improvement for Dial-a-Ride is the first progress for this problem in 15 years. To prove our main result, we consider the following generalization of the Minimum k-Edge Subgraph (Mk-ES) problem, which we call Min-Cost ℓ-Edge- Profit Subgraph (MCℓ-EPS): Given a graph G = (V, E) with edge-profits p = {pe : e �¸ E} and node-costs c = {cv : v �¸ V}, and a lower profit bound ℓ, find a minimum node-cost subgraph of G of edge-profit at least ℓ. The Mk-ES problem is a special case of MCℓ-EPS with unit node costs and unit edge profits. The currently best known ratio for Mk-ES is n3.2 �ã 2+ε [Chlamtac et al. 2012]. We extend this ratio to MCℓ-EPS for general node costs and profits bounded by a polynomial in n, which may be of independent interest.