Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
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.
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
Kafai Lai, Alan E. Rosenbluth, et al.
SPIE Advanced Lithography 2007
Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics
Trang H. Tran, Lam Nguyen, et al.
INFORMS 2022