Lisa Fleischer, Kamal Jain, et al.
Annual Symposium on Foundations of Computer Science - Proceedings
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 2 k of optimal. Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms. © 1995 Akadémiai Kiadó.
Lisa Fleischer, Kamal Jain, et al.
Annual Symposium on Foundations of Computer Science - Proceedings
Fabián A. Chudak, Michel X. Goemans, et al.
Operations Research Letters
Michel X. Goemans, David P. Williamson
Journal of the ACM (JACM)
Allan Borodin, Jon Kleinberg, et al.
Journal of the ACM