
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2000  Copyright 2000 Universität Bonn, Institut für Informatik, Abt. V  
85215

Improved Approximation of MAXCUT 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 3regular 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 2regular graphs. 

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