An Efficient Approximation Algorithm for the Survivable Network Design Problem

The survivable network design problem is to construct a minimum-cost subgraph satisfying certain given edge-connectivity requirements. The first polynomial-time approximation algorithm was given by Williamson et al. [21]. This paper gives an improved version that is more efficient. Consider a graph of n vertices and connectivity requirements that are at most k. Both algorithms find a solution that is within a factor 2k \Gamma 1 of optimal for k 2 and a factor 2 of optimal for k = 1. Our algorithm improves the time from O(k 3 n 4 ) to O(k 2 n 2 + kn 2 p log log n). Our algorithm shares features with [21] but also differs from it at a high level, necessitating a different analysis of correctness and accuracy; our analysis is based on a combinatorial characterization of the "redundant" edges. Several other ideas are introduced to gain efficiency. These include a generalization of Padberg and Rao's characterization of minimum odd cuts, use of a representation of all minimum (s; ..