Goemans-Williamson Algorithm

Purpose: A 0.878-approximation for MAX-CUT using semidefinite programming and random hyperplane rounding — the result that launched SDP-based approximation algorithms (1994).

The Problem

MAX-CUT: partition the vertices of a weighted graph into two sets to maximise the total weight of edges crossing the partition. NP-hard, and (unlike min cut) not solvable by flows.

Naive baseline: assign each vertex to a side by a coin flip. Each edge crosses with probability $1/2$, giving a 0.5-approximation in expectation. Local search (move any vertex that improves the cut) gives $0.5$ too. Goemans-Williamson beats both substantially.

The Algorithm

1. Relax. Write MAX-CUT as an integer quadratic program with $x_i\in \{-1,+1\}$:
   $\max {\sum }_{(i,j)\in E}{w}_{ij}\frac{1-x_i{x}_j}{2}.$
   Relax each scalar $x_i$ to a unit vector $v_i\in {\mathbb{R}}^n$:
   $\max {\sum }_{(i,j)\in E}{w}_{ij}\frac{1-⟨v_i,v_j⟩}{2},\Vert v_i\Vert =1.$
   This is a semidefinite program (the Gram matrix $X_{ij}=⟨v_i,v_j⟩$ must be PSD), solvable to arbitrary precision in polynomial time by interior-point methods.
2. Round. Draw a uniformly random hyperplane through the origin — i.e. a random Gaussian vector $r$ — and set
   $x_i=\mathrm{sign}(⟨v_i,r⟩).$
   Vertices on opposite sides of the hyperplane end up on opposite sides of the cut.

The Analysis

Two unit vectors at angle $\theta$ are separated by a random hyperplane with probability exactly $\theta /\pi$. The SDP’s contribution from that edge is $\frac{1-\cos \theta }{2}$. So the ratio for each edge is

$\frac{\theta /\pi }{(1-\cos \theta )/2}\ge {\min }_{0\le \theta \le \pi }\frac{2\theta }{\pi (1-\cos \theta )}=0.87856\dots$

The minimum is attained near $\theta \approx 2.331$ radians ($134°$). Summing over edges and using linearity of expectation gives

$\mathbb{E}[\text{cut}]\ge 0.878\cdot \mathrm{SDP}\ge 0.878\cdot \mathrm{OPT}.■$

Complexity

• SDP solution: polynomial, but with a large constant — practical up to a few thousand vertices
• Rounding: $O(n^2)$ per trial; repeat and keep the best
• Overall: polynomial, but not a competitive-programming tool

Optimality

Khot, Kindler, Mossel and O’Donnell showed that assuming the Unique Games Conjecture, no polynomial algorithm beats $0.878$ for MAX-CUT. Without UGC, the best unconditional hardness is $16/17\approx 0.941$. So Goemans-Williamson is very likely optimal — a rare and striking situation.

Why it matters conceptually

It established the template for modern approximation:

1. write the problem as an integer program;
2. relax to something convex (LP or SDP);
3. round the fractional solution randomly;
4. bound the loss from rounding.

The same recipe gives randomized rounding for set cover, sparsest cut, colouring, and constraint satisfaction generally.

Variants / Use Cases

• MAX-2SAT, MAX-DICUT, correlation clustering — the same SDP + hyperplane technique
• Randomized rounding — the LP version of the same idea
• Approximation Algorithms — the topic page
• In a contest — for a MAX-CUT-flavoured problem, use local search or simulated annealing; they have no guarantee but excellent practical quality