Past Awards
The 2006 John von Neumann Theory Prize is awarded by the Institute for Operations Research and the Management Sciences to Martin Grötschel, László Lovász and Alexander Schrijver for their fundamental path-breaking work in combinatorial optimization. Jointly and individually, they have made basic contributions to the analysis and solution of hard discrete optimization problems. In particular, their joint work on geometric algorithms based on the ellipsoid method of Yudin-Nemirovski and Shor showed the great power of cutting-plane approaches to such problems and provided a theoretical justification for the very active field of polyhedral combinatorics. One of the fundamental results was the equivalence of separation and optimization, discovered independently by three groups of researchers but developed in greatest depth by Grötschel, Lovász and Schrijver.
Martin Grötschel is a professor in the Technical University of Berlin and Vice-President of the Konrad Zuse Center for Information Technology. His early work with Manfred Padberg on the symmetric travelling salesman problem was a model for the use of polyhedral combinatorics techniques for solving hard combinatorial problems and he has continued to work with a large number of his graduate students and other researchers on applying these methods to spinglass problems in statistical physics, to circuit design, to network design, to vertex packing problems with Lovász and Schrijver and to the practical solution of applied problems in the computer and telecommunication industries as well as in public transportation systems. Grötschel served as the president of the German Mathematical Society and is a member of the German (Leopoldina) Academy of Sciences and a Foreign Associate of the US National Academy of Engineering.
László Lovász has held positions at universities in Hungary and the US as well as at Microsoft Research and is presently the director of the Mathematical Institute of the Eötvös Loránd University in Budapest. He first became well known when he proved the Perfect Graph Conjecture in 1972, at the age of 24. In 1979 he solved a long-standing problem of C. Shannon in coding theory by assigning vectors to the vertices of a graph and formulating an associated semidefinite programming problem; the approach has since become a powerful tool in attacking combinatorial optimization problems. In 1991, he and Schrijver showed the power of lift-and-project methods in 0-1 integer programming problems and the potential of semidefinite programming techniques to obtain tight relaxations. Lovász has also made key contributions to many topics in graph theory using novel techniques, to randomized algorithms and to submodular function minimization. Lovász will become the President of the International Mathematical Union next year. He is a member of the Hungarian, European, Russian and Dutch Academies of Sciences.
Alexander Schrijver is a researcher in the Probability, Networks and Algorithms Group of CWI, the national mathematics and computer science institute in the Netherlands, and a professor at the University of Amsterdam. In addition to the work mentioned above, he has investigated a wide range of hard problems from the theoretical to the applied: sensitivity and total dual integrality in integer programming, routing and timetabling in the Dutch railway system, Lovász 's theta function, certain polynomial homotopic routing problems in VLSI layout and a combinatorial algorithm to minimize submodular functions in strongly polynomial time. Schrijver is known for his impeccable scholarship in his monumental books on the Theory of Linear and Integer Programming and on Combinatorial Optimization. He is a member of the Dutch and German (Leopoldina and Nordrhine-Westfalian) Academies of Sciences.
Award presented by Uriel G. Rothblum, Chair, and Mark S. Daskin, President, November 6, 2006.