Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat
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 edges,
our implementation gives
O(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.