Michel X. Goemans, Joel M. Wein, et al.
Operations Research Letters
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ó.
Michel X. Goemans, Joel M. Wein, et al.
Operations Research Letters
Andreas S. Schulz, David B. Shmoys, et al.
PNAS
Fabián A. Chudak, Tim Roughgarden, et al.
Mathematical Programming
Alok Aggarwal, Jon Kleinberg, et al.
SIAM Journal on Computing