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 a single vertex vs. two distinct vertices from each group. The main contributions of our paper include the introduction of 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.

שפה מקוריתאנגלית
עמודים (מ-עד)55-64
מספר עמודים10
כתב עתTheoretical Computer Science
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 27 ינו׳ 2012

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

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

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