Jack Edmonds

Jack Edmonds, Professor in the Department of Combinatorics and Optimization at the University of Waterloo, has been awarded the 1985 John von Neumann Theory Prize. The citation reads as follows:

• Jack Edmonds has been one of the creators of the field of combinatorial optimization and polyhedral combinatorics. His 1965 paper "Paths, Trees and Flowers" was one of the first papers to suggest the possibility of establishing a mathematical theory of efficient combinatorial algorithms. In that paper and in the subsequent paper "Maximum Matching and a Polyhedron with 0-1 Vertices" Edmonds gave remarkable polynomial-time algorithms for the construction of maximum matchings. Even more importantly these papers showed how a good characterization of the polyhedron associated with a combinatorial optimization problem could lead via the duality theory of linear programming, to the construction of an efficient algorithm for the solution of that problem.
• During the 1960's, while working at the National Bureau of Standards, Edmonds explored the relationship between matroids and optimization. His beautiful theory of matroid partition and intersection remains one of the deepest results in the area. This work further illustrates the deep interconnections between combinatorial minmax theorems, polyhedral structure, duality theory and efficient algorithms. During this period he also made notable advances in the theory of network flow algorithms.
• In 1969 Edmonds moved to the University of Waterloo, where in collaboration with his many outstanding students, he has continued to explore combinatorial optimization problems and the associated polyhedra. His work during the past fifteen years has revolved around the theories of submodular functions, total dual integrality and oriented matroids.
• Throughout his career Edmonds has expended immeasurable time and effort assisting young researchers. Through his influence many outstanding young mathematicians have been drawn to the field of theoretical operations research.

For his deep and inspiring contributions to the field of combinatorial optimization we award Jack Edmonds the John von Neumann Theory prize.