Some experimental results on placement techniques
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
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. © 2011 Elsevier B.V. All rights reserved.
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
Charles H. Bennett, Aram W. Harrow, et al.
IEEE Trans. Inf. Theory
Raymond Wu, Jie Lu
ITA Conference 2007
Anupam Gupta, Viswanath Nagarajan, et al.
Operations Research