Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2000 Copyright 2000 Universität Bonn, Institut für Informatik, Abt. V

Improved Approximation of MAX-CUT on Graphs of Bounded Degree
Uriel Feige, Marek Karpinski and Michael Langberg
[Download PostScript] [Download PDF]

We analyze the addition of a simple local improvement step to various known randomized approximation algorithms. Let $\alpha\approx\simeq 0.87856$ denote the best approximation ratio currently known for the Max Cut problem on general graphs [GW95]. We consider a semidefinite relaxation of the Max Cut problem, round it using the random hyperplane rounding technique of ([GW95]), and then add a local improvement step. We show that for graphs of degree at most $\Delta$, our algorithm achieves an approximation ratio of at least $\alpha+\epsilon$, where $\epsilon>0$ is a constant that depends only on $\Delta$. In particular, using computer assisted analysis, we show that for graphs of maximal degree 3, our algorithm obtains an approximation ratio at least 0.921, and for 3-regular graphs, the approxiamtion ratio is at least 0.924. We note that for the semidefinite relaxation of Max Cut used in [GW95], the integrality gap is at least 1/0.884, even for 2-regular graphs.

Last Change: 11/05/14 at 10:17:35
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope