Approximating Fault-Tolerant Group-Steiner problems

Rohit Khandekar, Guy Kortsarz, Zeev Nutov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


In this paper, we initiate the study of designing approximation algorithms for Fault-Tolerant Group-Steiner (FTGS) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In Fault-Tolerant Group-Steiner problems, we are given a graph with edge- (or vertex-) costs, a root vertex, and a collection of subsets of vertices called groups. The objective is to find a minimum-cost subgraph that has two edge- (or vertex-) disjoint paths from each group to the root. We present approximation algorithms and hardness results for several variants of this basic problem, e.g., edge-costs vs. vertex-costs, edge-connectivity vs. vertex-connectivity, and 2-connecting from each group a single vertex vs. many vertices. Main contributions of our paper include the introduction of very general structural lemmas on connectivity and a charging scheme that may find more applications in the future. Our algorithmic results are supplemented by inapproximability results, which are tight in some cases. Our algorithms employ a variety of techniques. For the edge-connectivity variant, we use a primal-dual based algorithm for covering an uncrossable set-family, while for the vertex-connectivity version, we prove a new graph-theoretic lemma that shows equivalence between obtaining two vertex-disjoint paths from two vertices and 2-connecting a carefully chosen single vertex. To handle large group-sizes, we use a p-Steiner tree algorithm to identify the "correct" pair of terminals from each group to be connected to the root. We also use a non-trivial charging scheme to improve the approximation ratio for the most general problem we consider.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفFoundations of Software Technology and Theoretical Computer Science, FSTTCS 2009 - 29th Annual Conference, Proceedings
عدد الصفحات12
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2009
الحدث29th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009 - Kanpur, الهند
المدة: ١٥ ديسمبر ٢٠٠٩١٧ ديسمبر ٢٠٠٩

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

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت4
رقم المعيار الدولي للدوريات (المطبوع)1868-8969


!!Conference29th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009

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

Funding Information:
We would like to thank an anonymous referee for his comments that helped considerably improve the presentation of the paper. The second author was partially supported by NSF grant 08129959.


أدرس بدقة موضوعات البحث “Approximating Fault-Tolerant Group-Steiner problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا