An efficient approximation algorithm for the survivable network design problem

Abstract

The survivable network design problem (SNDP) 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. (Combinatorica 15 (1995) 435-454). 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 those of Williamson et al. (Combinatorica 15 (1995) 435-454) 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 (SIAM Journal on Computing 24 (1995) 296-317) for constrained forest problems such as minimum-weight matching, generalized Steiner trees and others. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.