A primal-dual approximation algorithm for generalized steiner network problems
作者： David P. Williamson , Michel X. Goemans , Milena Mihail , Vijay V. Vazirani
DOI: 10.1007/BF01299747
关键词:
摘要: We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least specified number of edges in each cut. This class problems includes, among others, generalized Steiner network problem, also called survivable design problem. Ifk is maximum cut requirement our solution comes within factor 2k optimal. Our primal-dual and shows importance this technique designing algorithms.
springer.com
sci-hub.se 参考文章(15)
Mechthild Stoer, Design of Survivable Networks ,(1992)
Philip Klein, R. Ravi, When Cycles Collapse: A General Approximation Technique for Constrained Two-Connectivity Problems integer programming and combinatorial optimization. pp. 39- 55 ,(1992)
M. X. Goemans, É. Tardos, S. Plotkin, A. V. Goldberg, D. P. Williamson, D. B. Shmoys, Improved approximation algorithms for network design problems symposium on discrete algorithms. pp. 223- 232 ,(1994) , 10.5555/314464.314497
Michel X. Goemans, David P. Williamson, A General Approximation Technique for Constrained Forest Problems SIAM Journal on Computing. ,vol. 24, pp. 296- 317 ,(1995) , 10.1137/S0097539793242618
Ajit Agrawal, Philip Klein, R. Ravi, When Trees Collide: An Approximation Algorithm for theGeneralized Steiner Problem on Networks SIAM Journal on Computing. ,vol. 24, pp. 440- 456 ,(1995) , 10.1137/S0097539792236237
A. Z. Zelikovsky, An 11/6-approximation algorithm for the network steiner problem Algorithmica. ,vol. 9, pp. 463- 470 ,(1993) , 10.1007/BF01187035
Michel X. Goemans, Dimitris J. Bertsimas, Survivable networks, linear programming relaxations and the parsimonious property Mathematical Programming. ,vol. 60, pp. 145- 166 ,(1993) , 10.1007/BF01580607
Ajit Agrawal, Philip Klein, R. Ravi, When trees collide: an approximation algorithm for the generalized Steiner problem on networks symposium on the theory of computing. pp. 134- 144 ,(1991) , 10.1145/103418.103437
Greg N. Frederickson, Joseph Ja’Ja’, Approximation Algorithms for Several Graph Augmentation Problems SIAM Journal on Computing. ,vol. 10, pp. 270- 283 ,(1981) , 10.1137/0210019
Kenneth Steiglitz, Christos H. Papadimitriou, Combinatorial Optimization: Algorithms and Complexity ,(1981)