A Faster Implementation of the Goemans-Williamson Clustering Algorithm

Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat

To appear, SODA, 2001.

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.