A primal-dual approximation algorithm for generalized Steiner network problems

Abstract

M.I.T. We present the first polynomial-time approxima-tion 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 solu-tion comes within a factor of 2k of optimal. Our algo-rithm is primal-dual and shows the importance of this technique in designing approximation algorithms. 1