A faster implementation of the Goemans-Williamson clustering algorithm

Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages17-25
Number of pages9
StatePublished - 2001
Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
Duration: Apr 30 2001May 1 2001

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other2001 Operating Section Proceedings, American Gas Association
Country/TerritoryUnited States
CityDallas, TX
Period4/30/015/1/01

Keywords

  • Algorithms
  • Theory
  • Verification

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'A faster implementation of the Goemans-Williamson clustering algorithm'. Together they form a unique fingerprint.

Cite this