Jack Edmonds
Encyclopedia
Jack R. Edmonds is a mathematician
, 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
.
He graduated from George Washington University
in 1958 and took a masters at the University of Maryland
in 1959, his thesis being on the problem of embedding graphs
into surfaces
(1959).
From 1959 to 1969 he worked at the National Institute of Standards and Technology
(then the National Bureau of Standards), being 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
. Edmonds retired in 1999.
From 1991 to 1993, he was involved in a dispute ("the Edmonds affair") with the University of Waterloo. The university claimed he had resigned, but he denied it. The conflict was resolved in 1993, and he returned to the university.
The Fifth Aussois Workshop on Combinatorial Optimization in 2001 was dedicated to Jack Edmonds.
Edmonds' matching algorithm and the research paper which describes this algorithm is one of the most cited papers. The Edmonds–Gallai decomposition theorem describes finite graphs from the point of view of matchings.
He introduced polymatroid
s. The Cobham–Edmonds thesis is named after him.
His son, Jeff Edmonds, is a Professor of Computer Science at York University
in Canada.
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
, regarded as one of the most important contributors to the field of combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
. He was the recipient of the 1985 John von Neumann Theory Prize
John von Neumann Theory Prize
The John von Neumann Theory Prize of the Institute for Operations Research and the Management Sciencesis awarded annually to an individual who has made fundamental and sustained contributions to theory in operations research and the management sciences.The Prize named after mathematician John von...
.
He graduated from George Washington University
George Washington University
The George Washington University is a private, coeducational comprehensive university located in Washington, D.C. in the United States...
in 1958 and took a masters at the University of Maryland
University of Maryland, College Park
The University of Maryland, College Park is a top-ranked public research university located in the city of College Park in Prince George's County, Maryland, just outside Washington, D.C...
in 1959, his thesis being on the problem of embedding graphs
into surfaces
(1959).
From 1959 to 1969 he worked at the National Institute of Standards and Technology
National Institute of Standards and Technology
The National Institute of Standards and Technology , known between 1901 and 1988 as the National Bureau of Standards , is a measurement standards laboratory, otherwise known as a National Metrological Institute , which is a non-regulatory agency of the United States Department of Commerce...
(then the National Bureau of Standards), being 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
University of Waterloo
The University of Waterloo is a comprehensive public university in the city of Waterloo, Ontario, Canada. The school was founded in 1957 by Drs. Gerry Hagey and Ira G. Needles, and has since grown to an institution of more than 30,000 students, faculty, and staff...
's Faculty of Mathematics
University of Waterloo Faculty of Mathematics
The Faculty of Mathematics is one of six faculties of the University of Waterloo in Waterloo, Ontario. As of Fall 2010, it has 5,741 undergraduate students and 629 graduate students, 200 full-time professors, and offers over 500 courses in mathematics, statistics and computer science.The Faculty...
. Edmonds retired in 1999.
From 1991 to 1993, he was involved in a dispute ("the Edmonds affair") with the University of Waterloo. The university claimed he had resigned, but he denied it. The conflict was resolved in 1993, and he returned to the university.
The Fifth Aussois Workshop on Combinatorial Optimization in 2001 was dedicated to Jack Edmonds.
Edmonds' matching algorithm and the research paper which describes this algorithm is one of the most cited papers. The Edmonds–Gallai decomposition theorem describes finite graphs from the point of view of matchings.
He introduced polymatroid
Polymatroid
In mathematics, polymatroid is a polytope associated with a submodular function. The notion was introduced by Jack Edmonds in 1970.-Definition:Consider any submodular set function f on S...
s. The Cobham–Edmonds thesis is named after him.
His son, Jeff Edmonds, is a Professor of Computer Science at York University
York University
York University is a public research university in Toronto, Ontario, Canada. It is Canada's third-largest university, Ontario's second-largest graduate school, and Canada's leading interdisciplinary university....
in Canada.
See also
- Chu–Liu/Edmonds algorithm
- Edmonds–Karp algorithm
- Edmonds matrix
- Edmonds's matching algorithmEdmonds's matching algorithmEdmonds's matching algorithmis an algorithm in graph theory for constructing maximum matchings on graphs. The algorithm was discovered by Jack Edmonds in 1965. Given a general graph G = , the algorithm finds a matching M such that each vertex in V is incident with at most one edge in M and |M| is...