World Library  
Flag as Inappropriate
Email this Article

Jack Edmonds

Jack R. Edmonds (born April 5, 1934) is an American computer scientist, regarded as one of the most important contributors to the field of combinatorial optimization. He was the recipient of the 1985 John von Neumann Theory Prize.


  • Research 1
  • Career 2
  • Personal life 3
  • See also 4
  • References 5
  • External links 6


A break through contribution of Edmonds is defining the concept of polynomial time characterising the difference between a practical and an impractical algorithm. Another of Edmonds' earliest and most notable contributions is the blossom algorithm for constructing maximum matchings on graphs, discovered in 1961,[1] and published in 1965.[2] This was the first polynomial-time algorithm for maximum matching in graphs. Its generalization to weighted graphs[3] was a conceptual breakthrough in the usage of linear programming ideas in combinatorial optimization. It sealed in the importance of there being proofs/witnesses that the answer for an instance is yes and there being proofs/witnesses that the answer for an instance is no.

Additional landmark work of Edmonds is in the area of matroids. He found a polyhedral description for all spanning trees of a graph, and more generally for all independent sets of a matroid.[4] Building on this, as a novel application of linear programming to discrete mathematics, he proved the matroid intersection theorem, a very general min-max combinatorial theorem[5][6] which, in modern terms, showed that the matroid intersection problem lay in both NP and co-NP.

Edmonds is well known for his theorems on max-weight branching algorithms[7] and packing edge-disjoint branchings[8] and his work with Richard Karp on faster flow algorithms. The Edmonds–Gallai decomposition theorem describes finite graphs from the point of view of matchings. He introduced polymatroids,[5] submodular flows with Richard Giles,[9] and the terms clutter and blocker in the study of hypergraphs.[1] A recurring theme in his work[10] is to seek algorithms whose time complexity is polynomially bounded by their input size and bit-complexity[1] (see the Cobham–Edmonds thesis).


Edmonds graduated with a baccalaureate degree from University of Maryland in 1959, with a thesis on the problem of embedding graphs into surfaces.

From 1959 to 1969 he worked at the National Institute of Standards and Technology (then the National Bureau of Standards), and was a founding member of Alan Goldman’s newly created Operations Research Section in 1961.

From 1969 on, with the exception of 1991-1993, he held a faculty position at the Department of Combinatorics and Optimization at the University of Waterloo's Faculty of Mathematics. He supervised the doctoral work of a dozen students in this time.

From 1991 to 1993, he was involved in a dispute ("the Edmonds affair") with the University of Waterloo,[11][12] wherein the university claimed that a letter submitted constituted a letter of resignation, which Edmonds denied.[13] The conflict was resolved in 1993, and he returned to the university.

Edmonds retired in 1999. The fifth Aussois Workshop on Combinatorial Optimization in 2001 was dedicated to him.[6]

Personal life

Jack's son Jeff Edmonds is a professor of computer science at York University, and his wife Kathie Cameron is a professor of mathematics at Laurier University.

See also


  1. ^ a b c Edmonds, Jack (1991), "A glimpse of heaven", in J.K. Lenstra, A.H.G. Rinnooy Kan, A. Schrijver, ed., History of Mathematical Programming --- A Collection of Personal Reminiscences, CWI, Amsterdam and North-Holland, Amsterdam, pp. 32–54 
  2. ^ Edmonds, Jack (1965). "Paths, trees, and flowers". Canad. J. Math. 17: 449–467.  
  3. ^ Edmonds, Jack (1965). "Maximum matching and a polyhedron with 0,1-vertices". Journal of Research National Bureau of Standards Section B 69: 125–130. 
  4. ^ Edmonds, Jack (1971). "Matroids and the greedy algorithm". Math. Programming (Princeton Symposium Math. Prog. 1967) 1: 127–136. 
  5. ^ a b Edmonds, Jack (1970), "Submodular functions, matroids, and certain polyhedra", in R. Guy, H. Hanam, N. Sauer, and J. Schonheim, editors, Combinatorial structures and their applications (Proc. 1969 Calgary Conference), Gordon and Breach, New York, pp. 69–87 .
  6. ^ a b Jünger, Michael and Reinelt, Gerhard and Rinaldi, Giovanni, ed. (2003), "Combinatorial Optimization -- Eureka, You Shrink!", Lecture Notes in Computer Science, vol. 2570 (Springer) 
  7. ^ Edmonds, Jack (1967). "Optimum Branchings". J. Res. Nat. Bur. Standards 71B: 233–240. 
  8. ^ Edmonds, Jack (1973), "Edge-disjoint branchings", Combinatorial Algorithms (Courant Computer Science Symposium 9, Monterey, California, 1972; R. Rustin, ed.) (Algorithmics Press, New York): 91–96 
  9. ^ Edmonds, Jack and Giles, Richard (1977), "A min-max relation for submodular functions on graphs", Studies in Integer Programming (Proceedings Workshop on Integer Programming, Bonn, 1975; P.L. Hammer, E.L. Johnson, B.H. Korte, G.L. Nemhauser, eds.), Annals of Discrete Mathematics (North-Holland, Amsterdam) 1: 185–204 
  10. ^ Christoph Witzgall (2001), "Paths, Trees, and Flowers", A Century of Excellence in Measurements, Standards, and Technology (PDF), National Institute of Standards and Technology, pp. 140–144 
  11. ^ UW Gazette, October 7, 1992: CAUT called in on Jack Edmonds case
  12. ^ Editor's introduction, in: Kenneth Westhues, ed., Workplace Mobbing in Academe: Reports from Twenty Universities, Lewiston: NY: The Edwin Mellen Press, 2004
  13. ^ University of Waterloo Daily Bulletin, March 5 2001: Conference honours Jack Edmonds

External links

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.