A primal-dual approximation algorithm for generalized Steiner network problems
David P. Williamson, Michel X. Goemans, Milena Mihail et al. · ACM Symposium on Theory of Computing (STOC) · 1993
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
Cited by 117 works. doi:10.1145/167088.167268 Open-access PDF
Authors
References
- Combinatorial Optimization: Algorithms and Complexity.
- A General Approximation Technique for Constrained Forest Problems
- An 11/6-approximation algorithm for the network steiner problem
- Design of Survivable Networks
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Improved Approximations for the Steiner Tree Problem
- Approximation Algorithms for Several Graph Augmentation Problems
- Survivable networks, linear programming relaxations and the parsimonious property
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Improved approximation algorithms for network design problems