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.
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
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.