AN APPROXIMATION ALGORITHM FOR MINIMUM-COST VERTEX-CONNECTIVITY PROBLEMS

We present an approximation algorithm for solving graph problems in wh ich a low-cost set of edges must be selected that has certain vertex-c onnectivity properties. In the survivable network design problem, a va lue r(ij) for each pair of vertices i and j is given, and a minimum-co st set of edges such that there are r(ij) vertex-disjoint paths betwee n vertices i and j must be found. In the case for which r(ij) is an el ement of (0, 1, 2) for all i, j, we can find a solution of cost no mor e than three times the optimal cost in polynomial time. In the case in which r(ij) = 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/n. No approxi mation algorithms were previously known for these problems. Our algori thms rely on a primal-dual approach which has recently led to approxim ation algorithms for many edge-connectivity problems.