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 (al ...
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
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
,
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 comb ...
,
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 continuous f ...
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 sci ...
(then the National Bureau of Standards), and was a founding member of
Alan Goldman Alan or Allan Goldman may refer to:
*Alan H. Goldman (born 1945), American philosopher
* Alan J. Goldman (1932–2010), American expert in operations research
* Alan S. Goldman (born 1958), American chemist
*Allan H. Goldman (born 1943), American re ...
’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 financed ...
-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
In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965.
Given a general graph , the algorithm finds a matching such that eac ...
for constructing
maximum matching
Maximum cardinality matching is a fundamental problem in graph theory.
We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adj ...
s 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 function#As a polynomial function, li ...
ideas in
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
. 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 ...
.
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 ...
, 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 by ...
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 of ...
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 not ...
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 proble ...
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
In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely ...
.
Edmonds is well known for his theorems on
max-weight branching algorithms[
] and packing edge-disjoint branchings
[
] and his work with
Richard Karp
Richard Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing A ...
on
faster flow algorithms. The
Edmonds–Gallai decomposition theorem describes finite graphs from the point of view of matchings. He introduced
polymatroid
In mathematics, a polymatroid is a polytope associated with a submodular function. The notion was introduced by Jack Edmonds in 1970. It is also described as the multiset analogue of the matroid.
Definition
Let E be a finite set and f: 2^E\rig ...
s,
submodular flows with Richard Giles,
[
] and the terms
clutter
Clutter and its derivations may refer to any of the following:
Excessive physical disorder
* Clutter, a confusing, or disorderly, state or collection, and possible symptom of compulsive hoarding
* Clutter (marketing), numerous advertisements, a ...
and blocker in the study of
hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
s.
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
The University of Waterloo (UWaterloo, UW, or Waterloo) is a public research university with a main campus in Waterloo, Ontario
Waterloo is a city in the Canadian province of Ontario. It is one of three cities in the Regional Municipality ...
's
Faculty of Mathematics
In contemporary education, mathematics education, known in Europe as the didactics or pedagogy of mathematics – is the practice of teaching, learning and carrying out scholarly research into the transfer of mathematical knowledge.
Although rese ...
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
The John von Neumann Theory Prize of the Institute for Operations Research and the Management Sciences (INFORMS)
is awarded annually to an individual (or sometimes a group) who has made fundamental and sustained contributions to theory in operati ...
.
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 sci ...
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
The Institute for Operations Research and the Management Sciences (INFORMS) is an international society for practitioners in the fields of operations research (O.R.), management science, and analytics. It was established in 1995 with the merger of ...
.
In 2006 the Queen of Denmark presented Edmonds with an Honorary Doctorate from the
University of Southern Denmark
The University of Southern Denmark ( da, Syddansk Universitet, lit=South Danish University, abbr. SDU) is a university in Denmark that has campuses located in Southern Denmark and on Zealand.
The university offers a number of joint programmes in ...
.
In 2014 he was honored as a Distinguished Scientist and inducted into the National Institute of Standards and Technology's Gallery.
The fifth
Aussois
Aussois () is a commune in the Vanoise massif, in the Savoie department in the Auvergne-Rhône-Alpes region in south-eastern France. The village is on the border of France's first National Park, the Vanoise National Park.
Although not as well ...
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 university, public research university in Toronto, Ontario, Canada. It is Canada's fourth-largest university, and it has approximately 55,700 students, 7,0 ...
, and his wife Kathie Cameron is a professor of mathematics at
Laurier University.
See also
*
Edmonds matrix
*
List of University of Waterloo people
The University of Waterloo, located in Waterloo, Ontario, Canada, is a comprehensive public university that was founded in 1957 by Drs. Gerry Hagey and Ira G. Needles. It has grown into an institution of more than 42,000 students, faculty, and ...
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