A primal-dual approximation algorithm for generalized Steiner network problems

We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut.This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem.If k is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal.Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.1