TR00-021 Authors: Uriel Feige, Marek Karpinski, Michael Langberg

Publication: 19th April 2000 14:45

Downloads: 1873

Keywords:

We analyze the addition of a simple local improvement step to various known

randomized approximation algorithms.

Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently

known for the Max Cut problem on general graphs~\cite{GW95}.

We consider a semidefinite relaxation of the Max Cut problem,

round it using the random hyperplane rounding technique of (\cite{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 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~\cite{GW95}, the integrality gap is at least $1/0.884$, even for

2-regular graphs.