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
עמודים263-274
מספר עמודים12
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2009
אירוע29th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009 - Kanpur, הודו
משך הזמן: 15 דצמ׳ 200917 דצמ׳ 2009

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

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך4
ISSN (מודפס)1868-8969

כנס

כנס29th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009
מדינה/אזורהודו
עירKanpur
תקופה15/12/0917/12/09

הערה ביבליוגרפית

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'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי