We present a factor 2 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, which is also known as the survivable network design problem. Our algorithm first solves the linear relaxation of this problem, and then iteratively rounds off the solution. The key idea in rounding off is that in a basic solution of the LP relaxation, at least one edge gets included at least to the extent of half. We include this edge into our integral solution and solve the residual problem.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received March 6, 1998
Rights and permissions
About this article
Cite this article
Jain, K. A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Combinatorica 21, 39–60 (2001). https://doi.org/10.1007/s004930170004
Issue Date:
DOI: https://doi.org/10.1007/s004930170004