A faster implementation of the Goemans-Williamson clustering algorithm

Richard Cole; Ramesh Hariharan; Moshe Lewenstein; Ely Porat

A faster implementation of the Goemans-Williamson clustering algorithm

Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 ² 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 language	English (US)
Title of host publication	Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages	17-25
Number of pages	9
State	Published - 2001
Event	2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States Duration: Apr 30 2001 → May 1 2001

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other	2001 Operating Section Proceedings, American Gas Association
Country/Territory	United States
City	Dallas, TX
Period	4/30/01 → 5/1/01

Keywords

Algorithms
Theory
Verification

ASJC Scopus subject areas

Software
General Mathematics

Cite this

A faster implementation of the Goemans-Williamson clustering algorithm. / Cole, Richard; Hariharan, Ramesh; Lewenstein, Moshe et al.
Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 2001. p. 17-25 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Cole, R, Hariharan, R, Lewenstein, M & Porat, E 2001, A faster implementation of the Goemans-Williamson clustering algorithm. in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 17-25, 2001 Operating Section Proceedings, American Gas Association, Dallas, TX, United States, 4/30/01.

@inproceedings{097bc625e6f945f9a5a2214cb64596e4,

title = "A faster implementation of the Goemans-Williamson clustering algorithm",

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.",

keywords = "Algorithms, Theory, Verification",

author = "Richard Cole and Ramesh Hariharan and Moshe Lewenstein and Ely Porat",

year = "2001",

language = "English (US)",

isbn = "0898714907",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

pages = "17--25",

booktitle = "Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms",

note = "2001 Operating Section Proceedings, American Gas Association ; Conference date: 30-04-2001 Through 01-05-2001",

}

TY - GEN

T1 - A faster implementation of the Goemans-Williamson clustering algorithm

AU - Cole, Richard

AU - Hariharan, Ramesh

AU - Lewenstein, Moshe

AU - Porat, Ely

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

KW - Algorithms

KW - Theory

KW - Verification

UR - http://www.scopus.com/inward/record.url?scp=65549163140&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=65549163140&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:65549163140

SN - 0898714907

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 17

EP - 25

BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 2001 Operating Section Proceedings, American Gas Association

Y2 - 30 April 2001 through 1 May 2001

ER -

A faster implementation of the Goemans-Williamson clustering algorithm

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this