Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-021 | 19th April 2000 00:00

Improved Approximation of MAX-CUT on Graphs of Bounded Degree

RSS-Feed

Abstract:

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.



ISSN 1433-8092 | Imprint