John S. Lew
Mathematical Biosciences
The survivable network design problem (SNDP) is the following problem: given an undirected graph and values ri j for each pair of vertices i and j, find a minimum-cost subgraph such that there are at least ri j disjoint paths between vertices i and j. In the edge connected version of this problem (EC-SNDP), these paths must be edge-disjoint. In the vertex connected version of the problem (VC-SNDP), the paths must be vertex disjoint. The element connectivity problem (ELC-SNDP, or ELC) is a problem of intermediate difficulty. In this problem, the set of vertices is partitioned into terminals and nonterminals. The edges and nonterminals of the graph are called elements. The values ri j are only specified for pairs of terminals i, j, and the paths from i to j must be element disjoint. Thus if ri j - 1 elements fail, terminals i and j are still connected by a path in the network. These variants of SNDP are all known to be NP-hard. The best known approximation algorithm for the EC-SNDP has performance guarantee of 2 and iteratively rounds solutions to a linear programming relaxation of the problem. ELC has a primal-dual O ( log k )-approximation algorithm, where k = maxi, j r i j. Since this work first appeared as an extended abstract, it has been shown that it is hard to approximate VC-SNDP to factor 2log1 - ε{lunate} n. In this paper we investigate applying iterative rounding to ELC and VC-SNDP. We show that iterative rounding will not yield a constant factor approximation algorithm for general VC-SNDP. On the other hand, we show how to extend the analysis of iterative rounding applied to EC-SNDP to yield 2-approximation algorithms for both general ELC, and for the case of VC-SNDP when ri j ∈ { 0, 1, 2 }. The latter result improves on an existing 3-approximation algorithm. The former is the first constant factor approximation algorithm for a general survivable network design problem that allows node failures. © 2006.
John S. Lew
Mathematical Biosciences
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
Kirsten Hildrum, Fred Douglis, et al.
ACM Transactions on Storage
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011