摘要: As noted in Section 12.3, the primal-dual schema is method of choice for designing approximation algorithms since it yields combinatorial with good factors and running times. We will first present central ideas behind this then use to design a simple f factor algorithm set cover, where frequency most frequent element.
springer.com
springerlink.com参考文章(9)
Michel X. Goemans, David P. Williamson, The primal-dual method for approximation algorithms and its application to network design problems Approximation algorithms for NP-hard problems. pp. 144- 191 ,(1996)
Dorit S. Hochba, Approximation Algorithms for NP-Hard Problems ,(1996)
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
R Bar-Yehuda, S Even, A linear-time approximation algorithm for the weighted vertex cover problem Journal of Algorithms. ,vol. 2, pp. 198- 203 ,(1981) , 10.1016/0196-6774(81)90020-1
H. W. Kuhn, The Hungarian method for the assignment problem Naval Research Logistics Quarterly. ,vol. 2, pp. 83- 97 ,(1955) , 10.1002/NAV.3800020109
G. B. Dantzig, L. R. Ford, D. R. Fulkerson, 7* A Primal-Dual Algorithm for Linear Programs Princeton University Press. pp. 171- 182 ,(1957) , 10.1515/9781400881987-008
David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani, A primal-dual approximation algorithm for generalized steiner network problems Combinatorica. ,vol. 15, pp. 435- 454 ,(1995) , 10.1007/BF01299747
George Bernard Dantzig, Albert W. Tucker, H. W. Kuhn, Linear Inequalities and Related Systems. ,(1956)