We give a deterministic polynomial-time algorithm which
for any given average degree $d$ and {\em asymptotically almost
all\/} random graphs $G$ in $\mathcal G(n, m=
\lfloor\frac{d}{2}n\rfloor)$ outputs a cut of $G$ whose ratio (in
cardinality) with the maximum cut is at least $0.952$. We remind
the reader that it is known that unless P=NP, for no constant
$\epsilon
>0$ is there a \textsc{Max-Cut} approximation algorithm
that for {\em all inputs} achieves an approximation ratio of
$(16/17) +\epsilon$ ($16/17 < 0.94118$).