Williamson Receives 2022 Steele Prize for Seminal Research Contribution

This story was adapted from a press release originally published on the American Mathematical Society website.

Michel Goemans and David Williamson, professor and chair of the Department of Information Science, 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 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.

Bio

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.