Goemans–Williamson: rounding geometry into a graph cut

What is recorded here?

Goemans and Williamson combine a semidefinite vector relaxation with random hyperplane rounding to obtain an expected approximately 0.87856 approximation for nonnegative weighted MAXCUT, with an epsilon loss for finite-precision optimization. Suppose a network must be split into two groups so that as much connection weight as possible crosses between them. Finding the best split is computationally hard in general. Michel X. Goemans and David P. Williamson temporarily replace each two-way choice with a direction on a sphere. A semidefinite program finds directions with a strong upper bound on the best discrete answer; a randomly chosen plane then turns the directions back into two groups. Geometry connects the probability of separating two directions to their angle. The resulting expected cut weight is at least about 87.856% of the optimum, allowing a small loss from approximate optimization. A single random split can perform worse. The work helped make semidefinite relaxation and geometric rounding useful tools for approximation algorithms, while building on earlier optimization and eigenvalue bounds. The 1995 journal version follows a 1994 conference paper and explicitly reports an error in the earlier proposed derandomization; these are one contribution family rather than two separate achievements.

Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.

Scientific scope

The approximation guarantee concerns the stated weighted Max-Cut model, semidefinite relaxation and randomized hyperplane rounding. It is an expected approximation ratio under the model, not exact optimization or a deterministic guarantee for every single random cut. Solving the relaxation to the required precision has a cost. Extensions and later optimality/hardness results are separate.

Read the original work

• Goemans and Williamson1995: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Karger, Motwani and Sudan: Approximate Graph Coloring by Semidefinite Programming

This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.

People and systems

Michel X. Goemans; David P. Williamson

Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.