# Improved approximation algorithm for steiner κ-Forest with nearly uniform weights

Michael Dinitz, Guy Kortsarz, Zeev Nutov

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

## תקציר

In the Steiner κ-Forest problem we are given an edge weighted graph, a collection D of node pairs, and an integer κ ≤ |D|. The goal is to find a minimum cost subgraph that connects at least κ pairs. The best known ratio for this problem is min{O( √n),O(√κ)} [8]. In [8] it is also shown that ratio ρ for Steiner κ-Forest implies ratio O(ρ · log2 n) for the Dial-a-Ride problem: given an edge weighted graph and a set of items with a source and a destination each, find a minimum length tour to move each object from its source to destination, but carrying at most κ objects at a time. The only other algorithm known for Dial-a-Ride, besides the one resulting from [8], has ratio O( √n) [4]. We obtain ratio n0.448 for Steiner κ-Forest and Dial-a-Ride with unit weights, breaking the O(√n) ratio barrier for this natural special case. We also show that if the maximum weight of an edge is O(nε), then one can achieve ratio O(n(1+ε)·0.448), which is less than √n if ε is small enough. To prove our main result we consider the following generalization of the Minimum κ-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+ε (note that 3-2√2 < 0.1716) [5]. We extend this ratio to MCℓ-EPS for arbitrary node weights and edge profits that are polynomial in n, which may be of independent interest.

שפה מקורית אנגלית Leibniz International Proceedings in Informatics, LIPIcs Klaus Jansen, Jose D. P. Rolim, Nikhil R. Devanur, Cristopher Moore Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing 115-127 13 9783939897743 https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.115 פורסם - 1 ספט׳ 2014 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 - Barcelona, ספרדמשך הזמן: 4 ספט׳ 2014 → 6 ספט׳ 2014

### סדרות פרסומים

שם Leibniz International Proceedings in Informatics, LIPIcs 28 1868-8969

### כנס

כנס 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 ספרד Barcelona 4/09/14 → 6/09/14