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 85215 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  English Universität Bonn -> Institut für Informatik -> Abteilung V