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. 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 – 1 of optimal for k ⩾ 2 and a factor 2 of optimal for k = 1. Our algorithm improves the time from O(k3n4) to O(k2n2+kn2 √(log log n)). Our algorithm shares features with that of Williamson et al. 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, t) cuts in a network, and a new priority queue system. The latter also improves the efficiency of the approximation algorithm of Goemans and Williamson for constrained forest problems such as minimum-weight matching, generalized Steiner trees and others.
