期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We analyze the addition of a simple local improvement step to various known
randomized approximation algorithms.
Let 087856 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 , our algorithm
achieves an approximation ratio of at least +, where
0 is a constant that depends only on .
In particular, using computer assisted analysis, we show that
for graphs of maximal degree 3, our algorithm obtains an approximation
ratio of at least 0921, and for 3-regular graphs, the approximation ratio
is at least 0924. We note that for the semidefinite relaxation of Max Cut
used in~\cite{GW95}, the integrality gap is at least 10884 , even for
2-regular graphs.
