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.