David P. Williamson, Michel X. Goemans
INFORMS Journal on Computing
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ó.
David P. Williamson, Michel X. Goemans
INFORMS Journal on Computing
Michel X. Goemans, David P. Williamson
SIAM Journal on Discrete Mathematics
Michel X. Goemans, David P. Williamson
Journal of the ACM (JACM)
Michel X. Goemans, Joel M. Wein, et al.
Operations Research Letters