@inproceedings{097bc625e6f945f9a5a2214cb64596e4,

title = "A faster implementation of the Goemans-Williamson clustering algorithm",

abstract = "We give an implementation of the Goemans-Williamson clustering procedure which is at the core of 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 implementation gives &Ogr; (k(n + m) log 2 n) time approximation algorithms for all these problems at the expense of a slight additive degradation of 1/n k in the approximation factor, for any constant k.",

keywords = "Algorithms, Theory, Verification",

author = "Richard Cole and Ramesh Hariharan and Moshe Lewenstein and Ely Porat",

year = "2001",

language = "English (US)",

isbn = "0898714907",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

pages = "17--25",

booktitle = "Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms",

note = "2001 Operating Section Proceedings, American Gas Association ; Conference date: 30-04-2001 Through 01-05-2001",

}