Jack Edmonds

Last updated
Jack Edmonds
Jack.Edmonds.jpg
Edmonds with his NP rock outside his home in Ontario, Canada
Born
John Robert Edmonds

(1934-04-05) April 5, 1934 (age 90)
Washington, D.C., U.S.
Alma mater
Known for
Awards John von Neumann Theory Prize (1985)
Scientific career
FieldsComputer Science, Mathematics
Institutions
Doctoral students

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.

Contents

Early career

Edmonds attended McKinley Technology High School, graduating in 1952; [1] and has talked about the influence this school had on his career (for instance at his 2014 NIST Gallery induction [2] [3] [4] ). 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. [5] [6] 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.

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 [7] and published in 1965. [8] This was the first polynomial-time algorithm for maximum matching in graphs. Its generalization to weighted graphs [9] 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. [10]

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 .

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 trees of a graph, and more generally for all independent sets of a matroid. [11] 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 [12] [13] 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 [14] and packing edge-disjoint branchings [15] 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, [12] submodular flows with Richard Giles, [16] and the terms clutter and blocker in the study of hypergraphs. [7] A recurring theme in his work [17] is to seek algorithms whose time complexity is polynomially bounded by their input size and bit-complexity. [7]

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. He gave courses or spent research leaves at Duke University, George Washington University, the University of Maryland, Stanford, Princeton, Cornell, as well as universities in China, Leuven (Belgium), Copenhagen, Southern Denmark (Odense), Paris, Marseille, Grenoble (France), as well as Bonn and Cologne (Germany).

From 1991 to 1993, he was involved in a dispute ("the Edmonds affair") with the University of Waterloo, [18] [19] wherein the university claimed that a letter submitted constituted a letter of resignation, which Edmonds denied. [20] 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, "Paths, 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. [21]

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. [13]

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

Related Research Articles

<span class="mw-page-title-main">Linear programming</span> Method to solve optimization problems

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements and objective are represented by linear relationships. Linear programming is a special case of mathematical programming.

<span class="mw-page-title-main">Greedy algorithm</span> Sequence of locally optimal choices

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

<span class="mw-page-title-main">Chinese postman problem</span> Finding shortest walks through all graph edges

In graph theory, a branch of mathematics and computer science, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undirected graph at least once. When the graph has an Eulerian circuit, that circuit is an optimal solution. Otherwise, the optimization problem is to find the smallest number of graph edges to duplicate so that the resulting multigraph does have an Eulerian circuit. It can be solved in polynomial time, unlike the Travelling Salesman Problem which is NP-hard. It is different from the Travelling Salesman Problem in that the travelling salesman cannot repeat visited nodes.

<span class="mw-page-title-main">Richard M. Karp</span> American mathematician

Richard Manning Karp 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 Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

<span class="mw-page-title-main">Combinatorial optimization</span> Subfield of mathematical 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 combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

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.

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 problem is to find a common independent set with the maximum possible weight. These problems generalize many problems in combinatorial optimization including finding maximum matchings and maximum weight matchings in bipartite graphs and finding arborescences in directed graphs.

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 G = (V, E), the algorithm finds a matching M such that each vertex in V is incident with at most one edge in M and |M| is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike bipartite matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph.

<span class="mw-page-title-main">Integral polytope</span> A convex polytope whose vertices all have integer Cartesian coordinates

In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it is a polytope that equals the convex hull of its integer points. Integral polytopes are also called lattice polytopes or Z-polytopes. The special cases of two- and three-dimensional integral polytopes may be called polygons or polyhedra instead of polytopes, respectively.

Eugene Leighton (Gene) Lawler was an American computer scientist and a professor of computer science at the University of California, Berkeley.

<span class="mw-page-title-main">Criss-cross algorithm</span> Method for mathematical optimization

In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic-programming problems, and linear complementarity problems.

In mathematics, a submodular set function is a set function that, informally, describes the relationship between a set of inputs and an output, where adding more of one input has a decreasing additional benefit. The natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory and electrical networks. Recently, submodular functions have also found utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, image collection summarization and many other domains.

In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or the spanning trees of a graph, among other applications.

In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks.

Komei Fukuda is a Japanese mathematician known for his contributions to optimization, polyhedral computation and oriented matroid theory. Fukuda is a professor in optimization and computational geometry in the Department of Mathematics and in the Institute of Theoretical Computer Science at ETH Zurich.

In convex geometry and polyhedral combinatorics, the extension complexity of a convex polytope is the smallest number of facets among convex polytopes that have as a projection. In this context, is called an extended formulation of ; it may have much higher dimension than .

In the theory of combinatorial optimization, submodular flow is a general class of optimization problems that includes as special cases the minimum-cost flow problem, matroid intersection, and the problem of computing a minimum-weight dijoin in a weighted directed graph. It was originally formulated by Jack Edmonds and Rick Giles, and can be solved in polynomial time.

The welfare maximization problem is an optimization problem studied in economics and computer science. Its goal is to partition a set of items among agents with different utility functions, such that the welfare – defined as the sum of the agents' utilities – is as high as possible. In other words, the goal is to find an item allocation satisfying the utilitarian rule.

References

  1. ↑ "Tech_alumni_pp48".
  2. ↑ https://www.nist.gov/system/files/documents/2017/05/09/Portrait-Gallery-Program-Brochure2014.pdf [ bare URL PDF ]
  3. ↑ "The Traveling Salesman Problem and P vs. NP: Some 1960s Theoretical Work at NIST on the Complexity of Mathematical Algorithms".
  4. ↑ https://math.nist.gov/mcsd/Seminars/2014/2014-10-10-Edmonds-presentation.pdf [ bare URL PDF ]
  5. ↑ "Jack Edmonds". The Mathematics Genealogy Project. Retrieved 23 June 2022.
  6. ↑ Edmonds Jr., John Robert (1960). A combinatorial representation for oriented polyhedral surfaces. hdl:1903/24820 . Retrieved 23 June 2022.
  7. 1 2 3 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
  8. ↑ Edmonds, Jack (1965). "Paths, trees, and flowers". Can. J. Math. 17: 449–467. doi: 10.4153/CJM-1965-045-4 . S2CID   247198603.
  9. ↑ Edmonds, Jack (1965). "Maximum matching and a polyhedron with 0,1-vertices". Journal of Research of the National Bureau of Standards Section B. 69 (1 and 2): 125–130. doi: 10.6028/jres.069B.013 .
  10. ↑ Meurant, Gerard (2014). Algorithms and Complexity. Elsevier. 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 [26] [1965, Paths, trees, and flowers]).
  11. ↑ Edmonds, Jack (1971). "Matroids and the greedy algorithm". Math. Programming (Princeton Symposium Math. Prog. 1967). 1: 127–136.
  12. 1 2 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..
  13. 1 2 Jünger, Michael; Reinelt, Gerhard; Rinaldi, Giovanni, eds. (2003), Combinatorial Optimization – Eureka, You Shrink!, Lecture Notes in Computer Science, vol. 2570, Springer
  14. ↑ Edmonds, Jack (1967). "Optimum Branchings". Journal of Research of the National Bureau of Standards Section B. 71B (4): 233–240. doi: 10.6028/jres.071B.032 .
  15. ↑ Edmonds, Jack (1973), R. Rustin (ed.), "Edge-disjoint branchings", Combinatorial Algorithms |Courant Computer Science Symposium 9, 1972, Monterey, California, 1972: Algorithmics Press, New York: 91–96{{citation}}: CS1 maint: location (link)
  16. ↑ 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 | Proceedings Workshop on Integer Programming, Bonn, 1975, Annals of Discrete Mathematics, 1, North-Holland, Amsterdam: 185–204, doi:10.1016/S0167-5060(08)70734-9, ISBN   9780720407655
  17. ↑ 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
  18. ↑ UW Gazette, October 7, 1992: CAUT called in on Jack Edmonds case
  19. ↑ 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
  20. ↑ University of Waterloo Daily Bulletin, March 5 2001: Conference honours Jack Edmonds
  21. ↑ Fellows: Alphabetical List, Institute for Operations Research and the Management Sciences, archived from the original on 2019-05-10, retrieved 2019-10-09
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.