Michel Goemans

The 2012 recipient of the Farkas Prize of the INFORMS Optimization Society, for Mid-Career Researchers, is Michel Goemans of MIT.

Michel Goemans has made fundamental contributions to the design and analysis of algorithms for discrete optimization problems; furthermore, his work on approximation algorithms has introduced many of the essential tools in this area, including semidefinite programming as well as a more sophisticated use of polyhedral combinatorics.

The two most influential of his papers, both joint with his PhD student David Williamson, gave breakthrough results for the maximum cut and minimum-cost Steiner forest problems. The first work gave a .878-approximation algorithm for the maximum cut problem, breaking a long-standing barrier of .5; subsequent work has shown that, subject to the unique games conjecture, this is best possible provided that P is not equal to NP. Goemans’s work introduced semidefinite programming as a tool in the design of approximation algorithms, thereby lifting the world of approximation algorithms from its focus on linear relaxations. Furthermore, it served as a catalyst in the development of algorithms for semidefinite programming as well as the further study of approximation algorithms based on embeddings in (geo)metric spaces.

Twenty-five years ago, it was widely believed that primal-dual techniques were of limited applicability in the domain of approximation algorithms. The second result of Goemans & Williamson mentioned above provided an elegant framework for capturing a wide swath of simple network design and connectivity problems, gave a simple, geometrically-inspired algorithm for computing good solutions, and then completed this work with an ingenious, but in retrospect transparent, analysis that the algorithm always delivers solutions of cost within a factor of two of optimal. Central to this achievement was the understanding of structural properties of the linear programming relaxation, which were then exploited in the remarkable analysis.

Goemans has consistently shown throughout his work that an in-depth understanding of polyhedral combinatorics can provide unexpected insights into the design of approximation algorithms. Nowhere is this more evident than in his relatively recent landmark achievement for the problem of computing a degree-bounded minimum spanning tree. Goemans gave an algorithm that finds a spanning tree of degree at most B+2, that is of cost no greater than the optimal cost of a spanning tree of degree at most B. (Previous results found only near-optimal cost trees with a logarithmic number of additional edges per node.) This sparked an avalanche of papers on degree-bounded network design,both improving the B+2 to B+1, as well as generalizing the settings in which similar results could be obtained.

Finally, Goemans’s recent result on the asymmetric traveling salesman problem (joint with Asadpour, Madry, Oveis Gharan, & Saberi) introduced a new suite of randomized rounding methods for the TSP, as well giving the first advance in 30 years by achieving an O( log n / log log n) performance guarantee. The ultimate impact of this breakthough is not yet known: the methods introduced here might still lead to the first constant-factor approximation algorithm for the asymmetric TSP, as well as to the first algorithm to improve upon Christofides’ classic result for the symmetric case.

Goemans’s contributions are marked by his innate ability to give the elegant solution; in fact, his knack of finding the beautiful proof (“from the book”) has led to a much deeper understanding of the work of many others as well. In summary, Michel Goemans is eminently deserving of the 2012 Farkas Prize awarded by the Optimization Society within the Institute for Operations Research and Management Science.

Selection committee

Monique Laurent, David Shmoys (Chair), Laurence Wolsey, Yinyu Ye.