|
Abstract : |
We analyze the addition of a simple local improvement step to various known randomized approximation algorithms. Let ff ' 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 ff + ffl, where ffl? 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 of at least 0:921, and for 3-regular graphs, the approximation 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. 1, |
