Optimization algorithms for energy-efficient data centers
Hendrik F. Hamann
InterPACK 2013
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.
Hendrik F. Hamann
InterPACK 2013
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
Zohar Feldman, Avishai Mandelbaum
WSC 2010
Marshall W. Bern, Howard J. Karloff, et al.
Theoretical Computer Science