Proc. ICALP '03
We consider the MAX k-CUT problem in random graphs G(n,p). First, we estimate the probable weight of a MAX k-CUT using probabilistic counting arguments and by analyzing a simple greedy heuristic. Then, we give an algorithm that approximates MAX k-CUT within expected polynomial time. The approximation ratio tends to 1 as np -> infinity. As an application, we obtain an algorithm for approximating the chromatic number of G(n,p), 1/n <= p <= 1/2, within a factor of O(sqrt{np}) in polynomial expected time, thereby answering a question of Krivelevich and Vu, and extending a result of Coja-Oghlan and Taraz. We give similar algorithms for random regular graphs G(n,r). Our main technical result is a bound on the probable value of Frieze and Jerrum's SDP-relaxation of MAX k-CUT, and may be of independent interest.