Brief Biography
Jack Edmonds is a John von Neumann Theory Prize recipient and one of the creators of combinatorial optimization. Edmonds attended George Washington University before pursuing graduate study at the University of Maryland. He received his master’s degree in 1959 and began work at the National Bureau of Standards (NBS).
Alan J. Goldman, Edmonds’s manager at the NBS arranged for Edmonds to participate in RAND Corporation-sponsored workshop in Santa Monica, California. At the time, most combinatorics scholars were not interested in algorithms. Edmonds was nevertheless intrigued by defining a class of algorithms that could run more efficiently and presented his findings to the group. These early investigations evolved into his work on the relationship between matroids and optimization that defined his early career.
In the 1960s, Edmonds developed a theory of matroid partition and intersection that still stands as one of the most profound and thorough explorations in the field. He illustrated the deep interconnections between combinatorial minmax theorems, polyhedral structure, duality theory, and efficient algorithms. His 1965 paper, “Paths, Trees, and Flowers," was one of the first to suggest the possibility of establishing a mathematical theory of efficient combinatorial algorithms. His work began to include other combinatorial optimization problems and associated polyhedra by the time he moved to the University of Waterloo in 1969. In 1972, he published an influential paper on theoretical improvements in algorithmic efficiency for network flow problems with University of California, Berkeley professor Richard M. Karp.
At Waterloo, Edmonds has supervised a dozen PhD students and continues a close professional relationship with many of them. Throughout his career, he has influenced and assisted numerous young researchers. He was awarded the John von Neumann Theory Prize for his contributions as a researcher and educator in 1985. Edmonds retired from teaching in 1999 and was elected into the inaugural Fellows class of the Institute for Operations Research and the Management Sciences.
Other Biographies
Wikipedia Entry for Jack Edmonds
Pulleybank W. R. (2012) Edmonds, Matching and the Birth of Polyhedral Combinatorics. Documenta Mathematica, Extra Volume ISMP: 181-197. (link)
Education
George Washington University, BS 1958
University of Maryland, MS 1959 (Mathematics Genealogy)
Affiliations
Academic Affiliations
- Center for Operations Research and Economics (CORE), Université Catholique de Louvain
- The George Washington University
- University of Maryland
- University of Waterloo
Non-Academic Affiliations
- National Institute of Standards and Technology/NIST (National Bureau of Standards/NBS)
- National Bureau of Standards
Key Interests in OR/MS
Methodologies
Memoirs and Autobiographies
Memoirs
Edmonds, J. (1991, based on an interview by George Nemhauser) A Glimpse of Heaven. Pages 32-54 in Lenstra JK, Rinnoy Kan AHG and Schrijver A eds. History of Mathematical Programming, CWI North Holland, Amsterdam 1991.
Awards and Honors
John von Neumann Theory Prize 1985
Institute for Operations Research and the Management Sciences Fellow 2002
Selected Publications
Edmonds J. (1965) Paths, trees, and flowers. Canadian Journal of Mathematics, 17(3): 449-467.
Edmonds J. (1967) Optimum branchings. Journal of Research of the National Bureau of Standards B, 71(4): 233-240.
Edmonds J. (1971) Matroids and the greedy algorithm. Mathematical Programming, 1(1): 127-136.
Edmonds J. & Johnson E. L. (1973) Matching, Euler tours and the Chinese postman. Mathematical Programming, 3(1), 88-124.
Edmonds J. & Karp R. M. (1972) Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2): 248-264.
Edmonds J. & Giles R. (1977) A min-max relation for submodular functions on graphs. Hammer P. L., Johnson E. L., & Korte B. H., eds. Studies in Integer Programming, 185-204. North Holland Publishing: Amsterdam.
Edmonds J. (1979). Matroid intersection. Annals of Discrete Mathematics, 4: 39-49.
Edmonds J., Lovász L., & Pulleybank W. R. (1982) Brick decompositions and the matching rank of graphs. Combinatorica, 2(3): 247-274.
Edmonds J. (2003) Submodular functions, matroids, and certain polyhedra. in Combinatorial Optimization—Eureka, You Shrink!, 11-26. Springer Heidelberg: Berlin.
Additional Resources
University of Waterloo. Water Under the Bridge: 1991. Accessed April 28, 2015. (link)