The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
How Good is the Geomans-Williamson Max Cut Algorithm?
Howard Karloff,
Pages. 336-350
Abstract The celebrated semidefinite programming algorithm for MAX CUP
introduced by Goemans and Williamson was known to have a
performance ratio of at least $alpha = frac{2}{pi} min_{0< heta leq pi}frac{ heta}{1-cos heta}$
(0.87856 $< alpha < $ 0.87857); the exact performance ratio was
unknown. We prove that the performance ratio of their algorithm is
exactly $alpha$. Furthermore, we show that it is impossible to
add valid linear constraints to improve the performance ratio.
Contents 1. Introduction 1.1. A description of Algorithm GW 2. Bounds on the performance ratio
Key words MAX CUT, semidefinite programming, approximation algorithm, optimization
Mathmatical Subject Classification 05C85, 49M37, 68Q25, 68R05, 68