A faster implementation of the Goemans-Williamson clustering algorithm
Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat · NOT FOUND REPOSITORY (Indian Institute of Science Bangalore) · 2001
We give an implementation of the Goemans-Williamson clustering procedure which is at thecore 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 edges, our implementation gives O \\Gamma k(n + m) log2 n\\Delta time approximation algorithms for allthese problems at the expense of a slight additive degradation of 1 nk in the approximation factor,for any constant k.