New upper bounds for the MAX CUT problem
Guangyan Zhou · Global Journal of Mathematical Analysis · 2014
Let $f_{cut}(n,cn)$ be the expectation of the value of the maximum cut of a given random graph G(n,cn) with n vertices and cn edges. We study the asymptotic change of $f_{cut}(n,cn)/cn$ as n tends to infinity with various densities c. In this paper, we provide new upper bounds by correcting the error items when applying the first moment method. Specifically, we extrapolate the region of c from c>1.386 to c>1.001.Keywords: MAX CUT, Upper Bound, Random Graph, First moment method.