This story originally published on the American Mathematical Society website.
Michel Goemans and David Williamson will receive the 2022 AMS Steele Prize for Seminal Contribution to Research for their paper "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming," published in 1995 in the Journal of the ACM. This paper, which focused on the Max‐Cut problem, a core problem in combinatorial optimization, has had major, sustained impact on the fields of theoretical computer science and optimization theory.
In their seminal work, Goemans and Williamson presented a new approximation algorithm for the Max‐Cut problem that yields an approximation ratio of 0.878. The algorithm introduced several key innovations that have become classic. This result and the systematic analysis procedure had an immediate and major impact—many related NP‐hard problems were studied via relaxation to semidefinite programs and approximation ratios were established and characterized for many problems. Moreover, over time, the result has grown in centrality and importance, with connections to complexity theory, cryptography, combinatorics, and algebra.
Response of Michel Goemans
I am delighted and deeply honored to receive the 2022 Leroy P. Steele Prize for Seminal Contribution to Research, together with David Williamson. This marvelous recognition was totally unexpected, and there are many contributions by other applied mathematicians who are deserving of this prize.
I would like to thank Laurence Wolsey, who taught me combinatorial optimization when I was an undergrad at UCLouvain. He got me passionate about it, and explicitly encouraged me to pursue a PhD at a top university in the US. That's how I ended up at the "Myth," as my mom would call "MIT" in her Italian accent.
My work over the years has been deeply influenced by the many transformative contributions of Laci Lovász and Lex Schrijver. When I learned about the so-called Lovász-Schrijver matrix cuts (for strengthening binary optimization problems) at a DIMACS workshop in 1989, I started wondering how tightly semidefinite relaxations can approximate various (hard) combinatorial problems. The simplest such problem to consider was fairly naturally the maximum cut problem. Although easy to state, the journey was long and the failures almost uncountable, even after enlisting the help of my first PhD student and collaborator, David Williamson.
Our aha moment came in September 1993 when David and I thought about using a random hyperplane to round the solution of our semidefinite relaxation, and thereby obtain provably good graph cuts in a completely (almost embarrassingly) elementary way. Semidefinite optimization is now a classical tool in approximating a wide range of hard algorithmic problems, and I am delighted that David and I had a role in making this happen.
Response of David Williamson
I'm very honored to be the co-winner of the Leroy P. Steele Prize with my PhD advisor, Michel Goemans. Let me express my gratitude to the selection committee for choosing our paper for the prize.
Michel and I worked out the idea of representing a cut by vectors and relaxing these to a semidefinite program during my years in graduate school. But then we got stuck on the question of how to extract a cut from the vectors, and we shelved the work for at least a year while I finished up my dissertation on an entirely different topic. I turned in my thesis and took a two-week vacation. On my return, we picked up the pieces again and during a two-hour meeting one Friday afternoon we hit on the idea of using a random hyperplane to partition the vectors. The analysis of the main result quickly followed. I sometimes tell my students (and myself) this story to explain why persistence is important and why one shouldn't give up too quickly on one's ideas.
I'm very grateful to all who helped me on my mathematical journey. While there are too many to list in this space, let me risk naming just a few. A high school math teacher, Donald G. McCloskey, inspired me by teaching an amazing pre-calculus class whose breadth opened up the mathematical landscape for me. He also had witty aphorisms that I still use with my own students today. My undergraduate advisor (now colleague), David Shmoys, involved me in research as a sophomore, and got me hooked on the area of discrete optimization and the joy of discovery. I was extremely fortunate to be Michel's first student; he was generous with his time and his friendship, and he taught me by example the beauties of simplicity and generality. Finally, my father, Jack Williamson, was for several decades a math professor at the University of Hawaii; he was supportive of all that I did, and I wish he could be here to see this.
Many thanks also to my children Abigail, Daniel, and Ruth, and to my wife Ann, for their love and encouragement.
Biographical Sketch of Michel Goemans
Michel Goemans is the RSA Professor in the Department of Mathematics at MIT and currently head of the department. Born in Belgium, he did his undergraduate studies at the University of Louvain (Belgium) in applied mathematics and his graduate studies at MIT. From 1997 to 1999, he held a professorship at UCLouvain while on leave from MIT. At MIT, he was the Robert E. Collins Distinguished Scholar in Mathematics in 2006-2007 and held the Leighton Family Professorship in Mathematics from 2007 to 2017. He has had an adjunct professorship at the University of Waterloo, Ontario, Canada, and a visiting professorship at RIMS, Kyoto, Japan.
Goemans' research is in optimization, combinatorics and algorithms. Over the years, he has developed a number of techniques for the design and analysis of efficient approximation algorithms for discrete optimization problems, with provable guarantees on the quality of the solution produced. He was a Sloan Fellow and a Guggenheim Fellow. For his research he was awarded the SIAM Optimization Prize (1996 and 1999), the Fulkerson Prize (2000), the Farkas Prize (2012), and most recently the Dantzig Prize (2021). He is a Fellow of the AMS, SIAM and ACM. He also received an honorary doctorate from UCLouvain.
Biographical Sketch of David Williamson
David Williamson was born in Madison, Wisconsin, but grew up in the suburbs of Honolulu, Hawaii. He received his PhD in 1993 from MIT. In 1995 he joined IBM Research, and from 2000 to 2003 was the Senior Manager of the Computer Science Principles and Methodologies Department at IBM's Almaden Research Center. In 2004, he joined Cornell University as a professor with a joint position in the School of Operations Research and Information Engineering and the Department of Information Science.
Williamson’s research interests lie in the area of discrete optimization, in particular approximation algorithms. He is a co-author of the book The Design of Approximation Algorithms, published by Cambridge University Press, which won the 2013 INFORMS Lanchester Prize. His PhD dissertation on designing low-cost survivable networks was awarded several prizes, including the 1994 Tucker Prize from the Mathematical Programming Society. His work with Michel Goemans on the uses of semidefinite programming has also been awarded several prizes, including the 2000 Fulkerson Prize. Williamson has served as an associate editor on several journals. He is an ACM Fellow and a SIAM Fellow.
About the Prize
The Steele Prize for Seminal Contribution to Research is awarded for a paper, whether recent or not, that has proved to be of fundamental or lasting importance in its field, or a model of important research. The prize is awarded according to the following six-year rotation of subject areas: Open, Analysis/Probability, Algebra/Number Theory, Applied Mathematics, Geometry/Topology, and Discrete Mathematics/Logic. The Steele Prizes were established in 1970 in honor of George David Birkhoff, William Fogg Osgood, and William Caspar Graustein, and are endowed under the terms of a bequest from Leroy P. Steele.
The 2022 prize will be presented Wednesday, January 5 during the Joint Prize Session at the 2022 Joint Mathematics Meetings in Seattle.