GoemansWilliamsonin

The Goemans–Williamson algorithm is a randomized approximation algorithm for the Max-Cut problem, introduced by Michel Goemans and David Williamson in 1995. It provides a guaranteed approximation ratio of at least about 0.878 for every instance, making it one of the most cited SDP-based approaches in combinatorial optimization.

The problem, Max-Cut, asks for a partition of the vertices of a graph into two groups to maximize the number of edges crossing the partition. The Goemans–Williamson method begins by solving a semidefinite programming relaxation of Max-Cut. In this relaxation, each vertex i is assigned a unit vector v_i in some high-dimensional space, and the objective is to maximize a function that depends on the pairwise inner products v_i · v_j for edges (i,j). The optimum of the SDP upper-bounds the true maximum cut value.

After obtaining the vectors, the algorithm performs a randomized rounding step: a random hyperplane through the origin is chosen, and vertices are placed on the two sides of the cut according to which side of the hyperplane their vector lies on. An edge (i,j) is cut if and only if v_i and v_j lie on opposite sides of the hyperplane. The probability that an edge is cut depends on the angle between v_i and v_j, leading to an expected cut value that is at least 0.878 times the SDP value, and hence at least 0.878 times the optimal cut.

The technique is influential in the study of approximation algorithms and SDP rounding, and it remains a benchmark for Max-Cut and related problems.