Cole, Richard ; Hariharan, Ramesh ; Lewenstein, Moshe ; Porat, Ely (2001) A faster implementation of the Goemans-Williamson clustering algorithm In: SODA '01 Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, January 07-09, 2001, Washington, D.C., USA.
Full text not available from this repository.
Official URL: http://dl.acm.org/citation.cfm?id=365411.365414
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 Ο (k(n + m) log2 n) time approximation algorithms for all these problems at the expense of a slight additive degradation of 1/nk in the approximation factor, for any constant k.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Source: | Copyright of this article belongs to ACM, Inc. |
| ID Code: | 102372 |
| Deposited On: | 09 Mar 2018 11:24 |
| Last Modified: | 09 Mar 2018 11:24 |
Repository Staff Only: item control page
