Lesson 8

Randomized approximation algorithm for Maximum Cut

In the maximum cut problem, the input is a graph, and the goal is to color its vertices with two colors so as to maximize the number of edges whose endpoints have different colors. Equivalently, one needs to partition the set of vertices into two parts so that as many edges as possible are cut. This problem has many applications: in image analysis, statistical physics, and chip design. Constructing an efficient exact algorithm for this problem is unlikely (it is NP-hard). It is interesting to note that (provably) the fastest known algorithm for this problem relies on fast matrix multiplication! Namely, the best known upper bound is \(2^{\frac{\omega n}{3}}\), where \(n\) is the number of vertices of the graph and \(\omega\) is the exponent of matrix multiplication. For this reason, approximation algorithms are actively studied. Such algorithms quickly find a solution that is guaranteed not to be much worse than the optimal one.

Constructing a \(1/2\)-approximation randomized algorithm for the maximum cut problem is especially simple: color each vertex independently at random with one of the two colors.

Problem. For a graph \(G(V,E)\), how many edges are cut this way?