Goemans and Williamson’s intuition
Recall that the Max-Cut problem is to, given a graph 
, find a division of 
into two sets such that the number of edges between the two sets is maximized. Here’s an interesting way, a la Lovasz, to motivate the Goemans-Williamson approximation to the solution the Max-Cut problem: embed the vertices of the graph onto the unit sphere in 
(
) and consider the energy given by
Maximize this energy; this tends to push adjacent vertices apart. Now cut the sphere with a random hyperplane passing through the origin. Since adjacent vertices are far apart, this cut will tend to separate them. Hence you suspect that this random cut might achieve close to the Max-Cut value.
It turns out that this algorithm achieves .878 of the Max-Cut value on average, which is pretty good, considering that it’s NP-hard to find a cut with more than about .94 of the Max-Cut value.
Possibly relevant posts:
- A do-it-yourself random graph result (5/21/2008)
- Connectedness of the set of feasible
-colorings (2/21/2007) - Spectral spread of Graphs (7/30/2010)