Heng Cao, Haifeng Xi, et al.
WSC 2003
We present an approximation algorithm for solving graph problems in which a low-cost set of edges must be selected that has certain vertex-connectivity properties. In the survivable network design problem, a value rij for each pair of vertices i and j is given, and a minimum-cost set of edges such that there are rij vertex-disjoint paths between vertices i and j must be found. In the case for which rij ∈ {0, 1, 2} for all i, j, we can find a solution of cost no more than three times the optimal cost in polynomial time. In the case in which rij = k for all i, j, we can find a solution of cost no more than 2H(k) times optimal, where H(n) = 1 + 1/2 + ⋯ + 1/2. No approximation algorithms were previously known for these problems. Our algorithms rely on a primal-dual approach which has recently led to approximation algorithms for many edge-connectivity problems.
Heng Cao, Haifeng Xi, et al.
WSC 2003
D.S. Turaga, K. Ratakonda, et al.
SCC 2006
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
Arnon Amir, Michael Lindenbaum
IEEE Transactions on Pattern Analysis and Machine Intelligence