Jack Edmonds

Born:
April 5, 1934

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
Non-Academic Affiliations

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)