We give a deterministic polynomial-time algorithm which for any given average degree d and asymptotically almost all random graphs G in G(n, m = [d/2 n]) 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 å>0 is there a Max-Cut approximation algorithm that for all inputs achieves an approximation ratio of (16/17) +å (16/17 < 0.94118).