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.
The Lanchester Prize for 2004 is awarded to Alexander Schrijver. He is being honored for his book Combinatorial Optimization: Polyhedra and Efficiency (Springer, 2003, Berlin: Heidelberg: New York).
This monumental work in three volumes is the most comprehensive in-depth survey to date of polyhedral combinatorics and polynomial-time algorithms for combinatorial optimization problems. Schrijver has meticulously documented both the mathematics and the history of numerous classical and progressive problems of combinatorial optimization, from paths, flows and matchings, to perfect graphs and submodular function minimization. The bibliography alone occupies about three hundred pages of the book. While some of the strongest results presented in this book were obtained by Schrijver himself, in many other cases he offered simpler proofs to results obtained by others.
It is worth mentioning that Schrijver previously won the 1986 Lanchester Prize for his excellent book Theory of Linear and Integer Programming. The winning book this year reflects Schrijver's remarkable journey to give the scientific community and future generations a superb, broad and deep account of the research developments in these mathematical areas of operations research. Schrijver's book will undoubtedly become an outstanding resource for researchers and students interested in polynomial-time algorithms for combinatorial optimization problems.
Two people were awarded the 1986 Lanchester Prize: Alexander Schrijver for his research monograph titled Theory of Linear and Integer Programming, and Peter Whittle for his research monograph Systems in Stochastic Equilibrium. Both works were published by John Wiley in 1986.
Theory of Linear and lnteger Programming by Alexander Schrijver is an outstanding contribution to the field of mathematical programming. This excellent treatment of the theoretical foundations of polyhedral optimization complements the many good books emphasizing practical algorithms for linear and integer programming. Schrijver deals effectively with standard results on the structure of polyhedra, polarity, and duality, often unifying and simplifying earlier approaches. Moreover, he gives detailed and penetrating presentations of many recent topics. For example the following are covered in some detail: the ellipsoid method and its theoretical implications, including the equivalence of separation and optimization; Lovasz's lattice basis reduction algorithm and its application to diophantine approximation; Lenstra's polynomial-time algorithm for integer programming with a fixed number of variables; Chvatal rank; cutting plane proofs; recognition of total unimodularity using Seymour's decomposition theorem; and integral polyhedra and total dual integrality. Schrijver also briefly treats such current topics as Karmarkar's algorithm, and the work of Megiddo and of Tardos on strongly polynomial algorithms. The exceptional scholarship of this work is revealed further in the extensive, and often fascinating historical notes at the end of each of the four parts into which the book is divided.
"Schrijver's book makes both the standard theory and the current developments in polyhedral optimization far more accessible. It is truly encyclopedic, and will serve as an indispensable reference for researchers, as well as an excellent text for advanced graduate students in this area. Accordingly, we award it the 1986 Lanchester Prize."