# 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, أسبانياالمدة: ٤ سبتمبر ٢٠١٤ → ٦ سبتمبر ٢٠١٤

### سلسلة المنشورات

الاسم Leibniz International Proceedings in Informatics, LIPIcs 28 1868-8969

### !!Conference

!!Conference 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 أسبانيا Barcelona ٤/٠٩/١٤ → ٦/٠٩/١٤