An approximation algorithm for minimum-cost vertex-connectivity problems
R. Ravi, David P. Williamson · 1995
Abstract. 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 ri) for each pair of vertices i and j is given, and a minimum-cost set of edges such that there are ri.i verlex-disjoint paths between vertices i and j must be found. In the case for which r 0 E 10. 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 2~(k) times optimal, where 7~(nl = 1 + 89 +... + ~.. No approximation algorithms were previously known for these problems. Our algorithms rely on a primal~lual approach which has recently led to approximation algorithms for many edge-connectivity problems. Key Words, Approximation algorithm, Vertex connectivity. Survivable network design, Primal-dual method.