Michel Goemans and David Williamson recently received the 2022 AMS Steele Prize for Seminal Contribution to Research for a 1995 paper which focused on the Max‐Cut problem, a core problem in combinatorial optimization, and has had sustained impact on the fields of theoretical computer science and optimization theory.

The Steele Prize is administered by the American Mathematical Socierty (AMS). It was originally established in 1970 in honor of George David Birkhoff, William Fogg Osgood, and William Caspar Graustein, endowed under the terms of a bequest from Leroy P. Steele. In 1993 the AMS formalized three categories of the prize, the other two being the Leroy P. Steele Prize for Lifetime Achievement and the Leroy P. Steele Prize for Mathematical Exposition. 

The Leroy P. Steele Prize for Seminal Contribution to Research, which carries a cash prize of $5,000, is awarded for a paper, whether recent or not, that has proved to be of fundamental or lasting importance in its field. It has a 6-year rotation of subject areas: Open, Analysis/Probability, Algebra/Number Theory, Applied Mathematics, Geometry/Topology, and Discrete Mathematics/Logic. The 2022 edition, which was in recognition of   "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming", published in November 1995 in the Journal of the ACM, was for Applied Mathematics. Nominations are now open for a paper in Geometry/Topology for the 2023 edition.

According to the AMS announcement:

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.

If you have never encountered the Max-cut problem it is very easy to state, but much more difficult to prove any conjecture about it. If you have a  graph - i.e. a network of nodes and their connections - the Max-cut problem is to find a cut, i.e, partition, of the network into two disjoint sets of nodes such that the number of edges that join two parts is as large as possible. Another way of thinking of it is to find two parts of the network that are maximally connected. This abstract problem isn't so abstract and has practical applications in physics and circuit layout.

Michel Goemans, who was already in the Department of Mathematics at MIT in 1995 and now heads it, explained:

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.

David Williamson was Goeman's first PhD student, then joined IBM Research and since 2004 is a professor at Cornell. He is the co-author of The Design of Approximation Algorithms. He recalled:

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.

The Max-cut problem is NP-hard and so any exact polynomial solution would imply that P=NP. Finding polynomial approximate solutions give us clues as to how an exact polynomial solution might be found - or throws light on why this is unlikely. 

Mike James is the author of The Programmer’s Guide To Theory which sets out to present the fundamental ideas of computer science in an informal, and yet informative, way and the The Trick Of The Mind: Programming and Computational Thought, which discusses how to think about problems from the perspective of maths and programming.

More Information

Michel Goemans and David Williamson receive 2022 Steele Prize for Seminal Contribution to Research

"Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming," by Michel X Goemans and David P. Williamson

Related Articles

Programmer's Guide To Theory - NP & Co-NP

Amoeba Solves Traveling Salesman Problem

What Is The Computational Power Of The Universe?

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN:0521195276>

<ASIN:B009019XCG>

<ASIN:1871962439> 

<ASIN:1871962730>