Jack R. Edmonds (born April 5, 1934) is an American-born and educated
computer scientist
A computer scientist is a person who is trained in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (a ...
and
mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of
combinatorial optimization,
polyhedral combinatorics Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.
Research in polyhedral co ...
,
discrete mathematics
Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuou ...
and the theory of computing. He was the recipient of the 1985 John von Neumann Theory Prize.
Early career
Edmonds attended Duke University before completing his undergraduate degree at George Washington University in 1957. He thereafter received a master's degree in 1960 at the University of Maryland under Bruce L. Reinhart 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
The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical s ...
(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
The RAND Corporation (from the phrase "research and development") is an American nonprofit global policy think tank created in 1948 by Douglas Aircraft Company to offer research and analysis to the United States Armed Forces. It is finance ...
-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.
Research
Edmonds's 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
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
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
Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds),.. asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is ...
.
A breakthrough of the
Cobham–Edmonds thesis
Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds),.. asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is ...
, was defining the concept of polynomial time characterising the difference between a practical and an impractical algorithm (in modern terms, a
tractable problem
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved b ...
or intractable problem). Today, problems solvable in polynomial time are called the
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms o ...
PTIME
In computational complexity theory, P, also known as PTIME or DTIME(''n''O(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, ...
, or simply
P.
Edmonds'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 tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is ...
s 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
In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection probl ...
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
In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an ...
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.
Career
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
The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical s ...
in their celebratory edition of A Century of Excellence in Measurements Standards and Technology
He was elected to the 2002 class of
Fellow
A fellow is a concept whose exact meaning depends on context.
In learned or professional societies, it refers to a privileged member who is specially elected in recognition of their work and achievements.
Within the context of higher education ...
s 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.
The fifth
Aussois Workshop on Combinatorial Optimization in 2001 was dedicated to him.
[
]
Personal life
Jack's son
Jeff Edmonds is a professor of computer science at
York University
York University (french: Université York), also known as YorkU or simply YU, is a public research university in Toronto, Ontario, Canada. It is Canada's fourth-largest university, and it has approximately 55,700 students, 7,000 faculty and sta ...
, and his wife Kathie Cameron is a professor of mathematics at
Laurier University.
See also
*
Edmonds matrix In graph theory, the Edmonds matrix A of a balanced bipartite graph G = (U, V, E) with sets of vertices U = \ and V = \ is defined by
: A_ = \left\{ \begin{array}{ll}
x_{ij} & (u_i, v_j) \in E \\
0 & (u_i, v_j) \notin E
\end{array}\right. ...
*
List of University of Waterloo people
References
External links
*
Biography of Jack Edmondsfrom the Institute for Operations Research and the Management Sciences
{{DEFAULTSORT:Edmonds, Jack
Combinatorialists
John von Neumann Theory Prize winners
20th-century Canadian mathematicians
University of Waterloo faculty
1934 births
Living people
Combinatorial optimization
Canadian computer scientists
Fellows of the Institute for Operations Research and the Management Sciences