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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 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

!!Conference17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014
الدولة/الإقليمأسبانيا
المدينةBarcelona
المدة٤/٠٩/١٤٦/٠٩/١٤

ملاحظة ببليوغرافية

Publisher Copyright:
© Michael Dinitz, Guy Kortsarz, and Zeev Nutov.

بصمة

أدرس بدقة موضوعات البحث “Improved approximation algorithm for steiner κ-Forest with nearly uniform weights'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا