Probability in Computer Science · Randomized Algorithms

Lesson 9

Nikolai Chukhin · Alexander S. Kulikov

It is not difficult to see that each edge is cut with probability exactly \(1/2\): there are four possible colorings \(\{00, 01, 10, 11\}\) of the endpoints of each edge, and in two of them the edge is cut. Hence, the expected number of cut edges equals \(|E|/2\).

For the curious 🤓

Improving upon the simple \(1/2\)-approximation algorithm for the maximum cut problem is challenging. An improvement was proposed by Goemans and Williamson in 1995. This algorithm also uses randomness! The maximum cut problem is formulated as an integer quadratic programming problem. Then each constraint of the form \(x \in \{-1,1\}\) is relaxed to \(-1 \le x \le 1\). This yields a semidefinite programming problem, for which one can (in polynomial time) find an almost exact solution. The obtained solution is rounded as follows: a random hyperplane through the origin is chosen, and all points lying on one side of this hyperplane are assigned the value \(-1\), while all others are assigned the value \(1\). The approximation guarantee of this algorithm is \(0.87854\). Perhaps surprisingly, the constant \(0.87854\) has been proved to be optimal under the Unique Games Conjecture. Moreover, under the conjecture that P\(\neq\) NP (which is widely believed), there exists no approximation algorithm achieving a ratio better than \(0.941\).