Goemans-Williamson Algorithm

The Goemans-Williamson algorithm is a semidefinite programming-based approximation algorithm for MAX-CUT, achieving an approximation ratio of α_GW ≈ 0.878..., which remains the best known guarantee for the problem. The algorithm works by solving an SDP relaxation that embeds the graph vertices onto a high-dimensional unit sphere, then partitioning the sphere with a random hyperplane to obtain a cut. The analysis is remarkably tight: the expected weight of the cut equals the SDP objective multiplied by exactly the Goemans-Williamson constant, and this factor is the best possible assuming the Unique Games Conjecture.

Beyond MAX-CUT, the Goemans-Williamson framework has become a template for approximation algorithms across combinatorial optimization. The method of randomized rounding — converting a continuous SDP solution into a discrete combinatorial object via a geometric random process — has been extended to constraint satisfaction problems, graph coloring, and scheduling. The algorithm's enduring importance lies not in the specific result but in the revelation that the geometry of convex relaxations can capture combinatorial structure in ways that linear programming cannot.