ECCC-Report TR00-021https://eccc.weizmann.ac.il/report/2000/021Comments and Revisions published for TR00-021en-usWed, 19 Apr 2000 14:45:31 +0300
Paper TR00-021
| Improved Approximation of MAX-CUT on Graphs of Bounded Degree |
Uriel Feige,
Marek Karpinski,
Michael Langberg
https://eccc.weizmann.ac.il/report/2000/021
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.
Wed, 19 Apr 2000 14:45:31 +0300https://eccc.weizmann.ac.il/report/2000/021