Jack Edmonds
Some quotes from Lex Schrijver’s 2000 page, 3 volume, slip-cased or CD, 87 euro book,
“Combinatorial Optimization : Polyhedra and Efficiency”, Springer, 2003 :
| “Pioneered by the work of Jack Edmonds, polyhedral combinatorics has proved to be a most powerful, coherent, and unifying tool throughout combinatorial optimization. Not only has it led to efficient (that is, polynomial-time) algorithms, but also, conversely, efficient algorithms often imply polyhedral characterizations and related min-max relations. It makes the two sides closely intertwined.” |
| “In the 1960s, Edmonds advocated calling an algorithm efficient [or “good”] if its running time is bounded by a polynomial in the size of its representation. Since then, this criterion has won broad acceptance, also because Edmonds found polynomial-time algorithms for several important combinatorial optimization problems.” |
| “Edmonds conjectured that there is no polynomial-time algorithm for the travelling salesman problem. In language that was developed later, this is equivalent to NP≠P.” |
In the paper, “Minimum Partition of a Matroid into Independent Sets”, 1965, Edmonds introduced the concept of NP (that is, existential polytime) and good characterizations (NP ∩ coNP) by using a parable of the absolute supervisor. The paper also introduced the concept of using black-box recognition of independence as an algorithmic oracle.
In published lectures (on ‘Polyhedral Combinatorics’) at the Calgary International Conference on Combinatorial Structures, Calgary, Alberta, 1969, he laid out main theorems about submodular functions, including a good characterization of the minimum of a submodular function, and the theorems which have been used many times since then in various algorithms for minimizing a submodular function.
Also in those lectures he presented with Dick Karp the first polynomial-time algorithms for network flows, and asked for strongly polynomial algorithms (i.e., which do not depend on bit-length of costs and capacities), achieved by Eva Tardos in 1985.
Also in those lectures he presented, with Ellis Johnson and Scott Lockhart, the software, ‘Blossom I’, which algorithmically unifies network flow problems and matching problems, using bidirected graphs, and provides the linear programming equivalent.
In 1964, Edmonds had already given the first polynomial-time version of Gaussian elimination for rational matrices (so that the bit-length stays non-exponential), and had posed the problem of determining the rank of a matrix of rational multivariate polynomials (in general still deterministically open, and sometimes called Edmonds’ matrix problem).
Around that time, helping Alfred Lehman with a project for Walter Reed Hospital, he introduced the graph isomorphism problem and solved it for trees. His write-up appeared, with an advocacy of polynomial time, in a graph theory book by Busacker and Saaty.
In the late 1970s with Arnaldo Mandel and Komei Fukuda, he derived the piecewise linear sphere-system representation of oriented-matroids, and used it to show non-degenerate cycling of Bland’s objective-based OM generalizations of the simplex method, and to describe some new non-cycling algorithms.
In the late 1970s with Kathie Cameron, and with Julian Araoz and others, he solved some combinatorial optimization problems by ‘extended formulations’.
Between 1975 and 1983, he had 15 successful PhD supervisions, more than the rest of his 120-professor math faculty. In the decade following he was isolated and constructively dismissed. He then devoted two years to collecting the support of a majority of the university’s regular faculty and to contesting successfully the dismissal. Sociology books have been based on this ‘Edmonds affair’.
Edmonds has never obtained a PhD for himself, except a 2006 honorary doctorate at the University of Southern Denmark in Odense where he chatted with the Queen.
In a Master’s degree essay he did do his ‘rotation-theorem’ which has become a well-known foundation of the field of graphs in surfaces. However while a PhD student in 1961 he dropped out of academia, not much approving of it.
In 1985, Edmonds was awarded the John Von Neumann Theory Prize by INFORMS.
Some quotes from the citation :
| “Jack Edmonds is one of the creators of the fields of combinatorial optimization and polyhedral combinatorics. |
| His 1965 paper “Paths, Trees and Flowers” was one of the first papers to suggest the possibility of establishing a mathematical theory of efficient combinatorial algorithms. […] |
| Edmonds gave remarkable polynomial-time algorithms for the construction of maximum matchings. Even more importantly, these papers showed 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. […] |
| His beautiful theory of matroid partition and intersection remains one of the deepest results in the area. This work further illustrates the deep interconnections between combinatorial min-max theorems, polyhedral structure, duality theory and efficient algorithms. […] |
| in collaboration with his many outstanding students, he continued to explore combinatorial optimization problems and the associated polyhedra. ... His work revolved around the theories of submodular functions, total dual integrality and oriented matroids. […] |
| Edmonds has expended immeasurable time and effort assisting young researchers. Through his influence many outstanding young mathematicians have been drawn to the field of theoretical operations research.” |
An ‘Existentially Polytime (EP) theorem’ is one which, like ‘good characterization’, asserts the existence of something any instance of which is easy to recognize relative to the size of the hypothesis-instance. Most of the structural existence theorems regarded by combinatorists as pretty are EP. In recent times, Edmonds has continued working to advocate studying algorithms which find an instance of what an EP theorem says exists –
For example, a direct algorithm for the theorem that :
| In any graph, there exists either a Berge obstruction or a clique and coloring the same size. |
Or for the theorem that :
| For any closed surface triangulation, and any subset of its triangles which partitions its vertices, there exists another different subset of its triangles which partitions its vertices. |
Or for the theorem that :
| For any Hamiltonian path P in a graph G such that G minus the edges of P is connected, there exists another different Hamiltonian path in G with the same ends as P. |