Edmonds with his NP rock outside his home in Ontario, Canada
John Robert Edmonds
April 5, 1934
|Alma mater||University of Maryland |
George Washington University
|Known for||NP |
Edmonds–Gallai decomposition theorem
|Awards||John von Neumann Theory Prize (1985)|
|Fields||Computer Science, Mathematics|
|Institutions||University of Waterloo|
National Institute of Standards and Technology
|Doctoral students||Peyton Young |
William R. Pulleyblank
Gilberto Calvillo Vives
Julian Araoz Durand
Jack R. Edmonds (born April 5, 1934) is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, polyhedral combinatorics, discrete mathematics and the theory of computing. He was the recipient of the 1985 John von Neumann Theory Prize.
Edmonds attended Duke University before completing his undergraduate degree at George Washington University in 1957. He thereafter pursued graduate studies at the University of Maryland 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. Goldman proved to be a crucial influence by enabling Edmonds to work in a RAND Corporation-sponsored workshop in Santa Monica, California. It is here that Edmonds first presented his findings on defining a class of algorithms that could run more efficiently. Most combinatorics scholars, during this time, were not focused on algorithms. However Edmonds was drawn to them and these initial investigations were key developments for his later work between matroids and optimization. He spent the years from 1961 to 1965 on the subject of NP versus P and in 1966 originated the conjectures NP ≠ P and NP ∩ coNP = P.
Edmonds 1965 paper “Paths, Trees and Flowers” was a preeminent paper in initially suggesting the possibility of establishing a mathematical theory of efficient combinatorial algorithms. One of his earliest and notable contributions is the blossom algorithm for constructing maximum matchings on graphs, discovered in 1961 and published in 1965. This was the first polynomial-time algorithm for maximum matching in graphs. Its generalization to weighted graphs was a conceptual breakthrough in the use of linear programming ideas in combinatorial optimization. It sealed in the importance of there being proofs, or "witnesses", that the answer for an instance is yes and there being proofs, or "witnesses", that the answer for an instance is no. In this blossom algorithm paper, Edmonds also characterizes feasible problems as those solvable in polynomial time; this is one of the origins of the Cobham–Edmonds thesis.
A breakthrough of the Cobham–Edmonds thesis, was defining the concept of polynomial time characterising the difference between a practical and an impractical algorithm (in modern terms, a tractable problem or intractable problem). Today, problems solvable in polynomial time are called the complexity class PTIME, or simply P.
Edmond's paper “Maximum Matching and a Polyhedron with 0-1 Vertices” along with his previous work gave astonishing polynomial-time algorithms for the construction of maximum matchings. Most notably, these papers demonstrated 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.
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. Building on this, as a novel application of linear programming to discrete mathematics, he proved the matroid intersection theorem, a very general combinatorial min-max theorem 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 and packing edge-disjoint branchings 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, submodular flows with Richard Giles, and the terms clutter and blocker in the study of hypergraphs. A recurring theme in his work is to seek algorithms whose time complexity is polynomially bounded by their input size and bit-complexity.
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 where his research encompassed combinatorial optimization problems and associated polyhedra. 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, wherein the university claimed that a letter submitted constituted a letter of resignation, which Edmonds denied. The conflict was resolved in 1993, and he returned to the university.
Edmonds retired from the University of Waterloo in 1999.
Awards and Honors
Edmonds was the 1985 recipient of the John von Neumann Theory Prize.
In 2001 his paper, "Path, Trees and Flowers" was honoured as an Outstanding Publication by the National Institute of Standards and Technology in their celebratory edition of A Century of Excellence in Measurements Standards and Technology
He was elected to the 2002 class of Fellows of the Institute for Operations Research and the Management Sciences.
In 2006 the Queen of Denmark presented Edmonds with an Honorary Doctorate from the University of Southern Denmark.
In 2014 he was honored as a Distinguished Scientist and inducted into the National Institute of Standards and Technology's Gallery.
- Edmonds, Jack (1991), "A glimpse of heaven", in J.K. Lenstra; A.H.G. Rinnooy Kan; A. Schrijver (eds.), History of Mathematical Programming – A Collection of Personal Reminiscences, CWI, Amsterdam and North-Holland, Amsterdam, pp. 32–54
- Edmonds, Jack (1965). "Paths, trees, and flowers". Can. J. Math. 17: 449–467. doi:10.4153/CJM-1965-045-4.
- Edmonds, Jack (1965). "Maximum matching and a polyhedron with 0,1-vertices". Journal of Research of the National Bureau of Standards Section B. 69: 125–130.
- Meurant, Gerard (2014). Algorithms and Complexity. p. p. 4. ISBN 978-0-08093391-7.
A problem is said to be feasible if it can be solved in polynomial time (as stated for the first time in Edmonds  [1965, Paths, trees, and flowers])).
- Edmonds, Jack (1971). "Matroids and the greedy algorithm". Math. Programming (Princeton Symposium Math. Prog. 1967). 1: 127–136.
- Edmonds, Jack (1970), "Submodular functions, matroids, and certain polyhedra", in R. Guy; H. Hanam; N. Sauer; J. Schonheim (eds.), Combinatorial structures and their applications (Proc. 1969 Calgary Conference), Gordon and Breach, New York, pp. 69–87.
- Jünger, Michael; Reinelt, Gerhard; Rinaldi, Giovanni, eds. (2003), "Combinatorial Optimization – Eureka, You Shrink!", Lecture Notes in Computer Science, Springer, 2570
- Edmonds, Jack (1967). "Optimum Branchings". J. Res. Nat. Bur. Standards. 71B: 233–240.
- Edmonds, Jack (1973), R. Rustin (ed.), "Edge-disjoint branchings", Combinatorial Algorithms, Monterey, California, 1972: Algorithmics Press, New York: 91–96CS1 maint: location (link)
- Edmonds, Jack; Giles, Richard (1977), P.L. Hammer; E.L. Johnson; B.H. Korte; G.L. Nemhauser (eds.), "A min-max relation for submodular functions on graphs", Studies in Integer Programming, Annals of Discrete Mathematics, North-Holland, Amsterdam, 1: 185–204
- 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, archived from the original (PDF) on 2006-03-25, retrieved 2011-08-11
- UW Gazette, October 7, 1992: CAUT called in on Jack Edmonds case
- Editor's introduction Archived 2010-10-27 at the Wayback Machine, in: Kenneth Westhues, ed., Workplace Mobbing in Academe: Reports from Twenty Universities, Lewiston: NY: The Edwin Mellen Press, 2004
- University of Waterloo Daily Bulletin, March 5 2001: Conference honours Jack Edmonds
- Fellows: Alphabetical List, Institute for Operations Research and the Management Sciences, archived from the original on 2019-05-10, retrieved 2019-10-09