Lisa Fleischer, Kamal Jain, et al.
Journal of Computer and System Sciences
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.
Journal of Computer and System Sciences
Takao Asano, David P. Williamson
Journal of Algorithms
R. Ravi, David P. Williamson
SODA 2002
Tomás Feder, Milena Mihail
STOC 1992