Improved Approximation Algorithm for Steiner k -Forest with Nearly Uniform Weights
Michael Dinitz, Guy Kortsarz, Zeev Nutov · ACM Transactions on Algorithms · 2017
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 a min-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 (ρ · log 2 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 n 0.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 + ϵ) · 0.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 (M k -ES) problem, which we call Min-Cost ℓ-Edge-Profit Subgraph (MCℓ-EPS): Given a graph G = ( V , E ) with edge-profits p = { p e : e ∈ E } and node-costs c = { c v : v ∈ V }, and a lower profit bound ℓ, find a minimum node-cost subgraph of G of edge-profit at least ℓ. The M k -ES problem is a special case of MCℓ-EPS with unit node costs and unit edge profits. The currently best known ratio for M k -ES is n 3-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.