Goemans

Goemans is a surname. Notable individuals with the name include Michel X. Goemans, a Belgian-American computer scientist and mathematician known for work in approximation algorithms and combinatorial optimization. He is best known for co-developing the Goemans–Williamson algorithm for the Max-Cut problem with David P. Williamson.

The Goemans–Williamson algorithm is a landmark result in the field of approximation algorithms. It was introduced in 1995 and provides a guaranteed approximation ratio of approximately 0.87856 for the Max-Cut problem. The method begins by relaxing Max-Cut to a semidefinite programming (SDP) problem, yielding a feasible solution in the form of unit vectors assigned to the graph’s vertices. It then uses a random hyperplane through the origin to partition these vectors into two sets, with the cut determined by the sign of the projection onto the hyperplane. The expected weight of the resulting cut is at least 0.87856 times the optimum of the SDP, and hence at least that fraction of the true optimum Max-Cut value.

Impact from this work has been substantial. The algorithm is widely cited as a key development in SDP-based approximation and has influenced a broad class of rounding techniques used to convert continuous relaxations into combinatorial solutions. It helped establish semidefinite programming as a powerful tool in designing approximation algorithms and stimulated further research in graph partitioning and related optimization problems.