How good is the Goemans{Williamson MAX CUT algorithm?

Authors
Karloff, H
Citation
H. Karloff, How good is the Goemans{Williamson MAX CUT algorithm?, SIAM J COMP, 29(1), 1999, pp. 336-350
Citations number
8
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
29
Issue
1
Year of publication
1999
Pages
336 - 350
Database
ISI
SICI code
0097-5397(19990922)29:1<336:HGITGM>2.0.ZU;2-5
Abstract
The celebrated semidefinite programming algorithm for MAX CUT introduced by Goemans and Williamson was known to have a performance ratio of at least [GRAPHICS] (0: 87856 < < 0: 87857); the exact performance ratio was unknown. We prove that the performance ratio of their algorithm is exactly. Furthermore, we s how that it is impossible to add valid linear constraints to improve the pe rformance ratio.