The Goemans-Williamson Algorithm

Consider the problem of finding the Max-Cut in a weighted graph $G =(V, E, w)$
It is known to be NP-complete to decide if the maximum cut is bigger than some parameter $k$ . It’s NP-hard to even approximate the Max-Cut to an approximate ratio of $\frac{16}{17}$ (unless $P=NP$ )

If we pick the cut randomly, that is if we decide randomly whether to include a vertex or not on the left side, the expected cost of the cut is half the total cost of the graph. Hence it is at least half of the Max-Cut value and gives a $\frac{1}{2}$ approximation. In fact, a greedy deterministic algorithm also gives you the same approximation factor. Start with a trivial partition, and move the vertices around –if the cost of cut edges from a vertex exceeds the cost from internal edges, move the vertex to the other side– this flips the cut edges and internal edges and increases the cost.

The Goemans-Williamson algorithm is a randomized algorithm that achieves, on expectation, an approximation factor of

$\displaystyle \alpha_{GW}:=\min_{x \in(-1,0)} \frac{2}{\pi} \frac{\arccos x}{1-x} \approx 0.878 .$

The algorithm is based on a semi-definite relaxation of the Max-Cut problem. Note that the Max-Cut can be seen as a quadratic integer program given by:

$\displaystyle \max \sum_{(u, v) \in E} w_{u v}\left(\frac{1-x_{u} x_{v}}{2}\right), x_i \in \{-1, 1 \}$

We relax the condition $x \in \{-1, 1\}$ to $\vec{x} \in \mathbb R^n : \| \vec{x}\|=1$ and consider the semidefinite program

$\displaystyle \max \sum_{(u, v) \in E} w_{u v}\left(\frac{1-\vec{x}_{u} \cdot \vec{x}_{v}}{2}\right)$

Now once we solve for the semidefinite program, we round the fractional solutions to get approximations to the Max-Cut. We take a random hyperplane and set the values of vectors on one side to $-1$ and the opposite side to $1$ .

Note that the fractional solution has contribution $w_{uv} \left(\frac{1-\cos {\theta}}{2}\right)$ for an edge; on the other hand on the probability that $\vec{x}_u &fg=00000$ and $\vec{x}_v$ fall on opposite sides of the random hyperplane and hence contribute to the cost is given by $w_{uv} \frac{\theta}{\pi}$ .