AN EFFICIENT APPROXIMATION ALGORITHM FOR THE SURVIVABLE NETWORK DESIGN PROBLEM

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 Willi amson et al, (Combinatorica 15 (1995) 435-454). This paper gives an im proved 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 greater th an or equal to 2 and a factor 2 of optimal for k = 1. Our algorithm im proves the time from O(k(3)n(4)) to O(k(2)n(2) + kn(2) root log log n) . Our algorithm shares features with those of Williamson et al, (Combi natorica 15 (1995) 435-454) out also differs from it at a high level, necessitating a different analysis of correctness and accuracy; our an alysis 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 min imum 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 th e efficiency of the approximation algorithm of Goemans and Williamson (SIAM Journal on Computing 24 (1995) 296-317) for constrained forest p roblems such as minimum-weight matching, generalized Steiner trees aci d others. (C) 1998 The Mathematical Programming Society, Inc. Publishe d by Elsevier Science B.V.