I plan to write a few posts about approximation algorithms. I decided to start with my favorite one, and the first non-trivial one I read about, the SDP relaxation for Max-Cut. This post will be about this particular approximation algorithm and the proof for its guarantee.

The objective of approximation algorithms is to efficiently compute approximate solutions to problems for which finding an exact solution is believed to be computationally hard. In order to illustrate this we will look into the Max-Cut problem. Given a graph with non-negative weights on the edges. The Max-Cut problem is that of finding a set such that is maximal.

The Max-Cut problem is known to be NP-hard (if the widely believed conjecture is true this means that the problem cannot be solved in polynomial time). On what follows we will show a randomized algorithm of Goemans and Williamson that is able to, in polynomial time, obtain a cut whose expected value is guaranteed to be no smaller than a particular constant times the optimum cut.

Let . One can restate the problem has

We consider the following relaxation of this problem:

Note that this is in fact a relaxation because if one would restrict to maximizing multiple of , the first element of the canonical basis, the problem would be equivalent to the original.

From the solution of the relaxed problem one can produce a cut subset by randomly picking an vector from the uniform distribution on the unit sphere and letting . In order for this algorithm to be of interest two things must happen: The relaxed problem needs to be significantly easier to solve than the original and the cut given by the set needs to be comparable to the optimal one. We will start by showing the latter.

Let be the value of the cut produced by the relaxation described above. Clearly is a random variable, it’s expectation is

It is not hard to show (see here) that

where .

Let be the maximum cut of , meaning the maximum of the original problem. It is easy to see that the solution to the relaxed version is larger or equal than . Hence,

showing that the algorithm based on the relaxation has a performance guarantee (in expectation) of .

What makes all this interesting is the fact that one can obtain a solution of the relaxed problem in a trackable way. If we set where has the vectors as its columns (it is called the Gram Matrix of then we can rewrite the objective function of the relaxed problem as . One can exploit the fact that having a decomposition of the form is equivalent to being positive Semi-Definite , which is a convex constraint. Also, the constraint that can be rewritten has . This implies that the relaxed problem is equivalent to the following Semi-Definite program:

Since a Semi-Definite Program can be solved (up to accuracy) in time growing only polynomial on the input data and this describes a randomized algorithm for Max-Cut with a performance guarantee.

Sometimes randomized algorithms blow my mind, and this is a perfect example. Thanks for the post. FYI – I think the inequality is going the wrong way in (3), and your v’s turned into y’s in the discussion before (5).

Hi Dustin,

The algorithm is pretty impressive yes! Even more impressive is the fact that, if you believe Unique Games Conjecture and , then this algorithm is tight — There is no polynomial time algorithm that is able to get a better approximation performance.

Thanks for catching the typos!

Afonso