Michel X. Goemans, David P. Williamson
SIAM Journal on Discrete Mathematics
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, David P. Williamson
SIAM Journal on Discrete Mathematics
Fabián A. Chudak, Tim Roughgarden, et al.
Mathematical Programming
Allan Borodin, Jon Kleinberg, et al.
STOC 1996
David P. Williamson, Michel X. Goemans
INFORMS Journal on Computing