A faster implementation of the Goemans-Williamson clustering algorithm
作者： Ely Porat , Moshe Lewenstein , Ramesh Hariharan , Richard Cole
关键词: Cluster analysis 、 Enhanced Data Rates for GSM Evolution 、 Graph (abstract data type) 、 Steiner tree problem 、 Core (graph theory) 、 Travelling salesman problem 、 Approximation algorithm 、 Constant (mathematics) 、 Combinatorics 、 Computer science
摘要: We give an implementation of the Goemans-Williamson clustering procedure which is at core several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting Travelling Salesman, 2-Edge Connected Subgraph etc. On a graph with n nodes and m edge, our gives O (k(n + m) log2n) time all these problems expense slight additive degradation 1/nk in factor, any constant k.
acm.org
hariharan-ramesh.com 
researchgate.net 参考文章(7)
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)
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
Maria Minko, David R Karger, The prize collecting Steiner tree problem: theory and practice symposium on discrete algorithms. pp. 760- 769 ,(2000) , 10.5555/338219.338637
Philip N. Klein, A data structure for bicategories, with application to speeding up an approximation algorithm Information Processing Letters. ,vol. 52, pp. 303- 307 ,(1994) , 10.1016/0020-0190(94)00156-1
Harold N. Gabow, Michel X. Goemans, David P. Williamson, An efficient approximation algorithm for the survivable network design problem Mathematical Programming. ,vol. 82, pp. 13- 40 ,(1998) , 10.1007/BF01585864
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