AMS Award For Max Cut Algorithm |

Written by Mike James | |||

Sunday, 30 January 2022 | |||

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 According to the AMS announcement:
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:
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 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.
,The Trick Of The Mind: Programming and Computational Thoughtwhich discusses how to think about problems from the perspective of maths and programming. ## More InformationMichel Goemans and David Williamson receive 2022 Steele Prize for Seminal Contribution to Research
## Related ArticlesProgrammer'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
or email your comment to: comments@i-programmer.info <ASIN:0521195276> <ASIN:B009019XCG> <ASIN:1871962439> <ASIN:1871962730> |
|||

Last Updated ( Sunday, 30 January 2022 ) |