A primal-dual approximation algorithm for generalized steiner network problems |
| |
| Authors: | David P. Williamson Michel X. Goemans Milena Mihail Vijay V. Vazirani |
| |
| Affiliation: | (1) IBM T. J. Watson Research Center, Room 33-219 Route 134, 10598 Yorktown Heights, NY, USA;(2) Department of Mathematics, MIT, Room 2-382, 02139 Cambridge, MA, USA;(3) Bellcore, 445 South Street, 07960 Morristown, NJ, USA;(4) Computer Science and Engineering Department, Indian Institute of Technology, 110016 New Delhi, India |
| |
| Abstract: | 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. Ifk is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal. Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.Research supported by an NSF Graduate Fellowship, DARPA contracts N00014-91-J-1698 and N00014-92-J-1799, and AT&T Bell Laboratories.Research supported in part by Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.Part of this work was done while the author was visiting AT&T Bell Laboratories and Bellcore. |
| |
| Keywords: | 05 C 40 68 Q 25 90 C 10 90 C 35 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
