First Mathematical Theory of Efficient Combinatorial Algorithms: Jack Edmonds

Date: 1965

One of the creators of the fields of combinatorial optimization, polyhedral combinatorics, and computational complexity theory, NIST’s Jack Edmonds helped identify what is perhaps the most sought-after question in computer science research today: Is P=NP?

Jack Edmonds is widely acknowledged as one of the creators of the fields of combinatorial optimization and polyhedral combinatorics, which emerged during the period of Edmond’s tenure at NBS (1959-69). Combinatorial optimization is the process of identifying the “best” from a finite (but often very large) set of choices. A classic example is the well-known travelling salesman problem. Polyhedral combinatorics studies the relationship between counting problems and geometric objects, thus enabling geometrical reasoning to be applied the solution of challenging counting and optimization problems. The foundation of modern operations research, combinatorial optimization is routinely used today in such areas as vehicle routing, class scheduling, bin packing, and target assignment.

In recognition for his contributions to this field, Edmonds was awarded the prestigious John von Neumann Theory Prize by The Institute for Operations Research and the Management Sciences^[1] (INFORMS) in 1985. In the citation for that award, two of Edmonds’ NBS publications are explicitly mentioned [1, 2]: 

“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. In that paper and in the subsequent paper Maximum Matching and a Polyhedron with 0-1 Vertices 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.”  

Edmonds’ work at NBS also laid foundations for the newly emerging field of computer science. In fact, his early work led to the characterization of one of today’s most important open questions in the theory of computation. As demonstrated by its inclusion as one of the Clay Mathematics Institute’s Millennial Problems^[2], a central question in theoretical computer science is whether or not the class of problems whose solutions can be verified in time that grows like a polynomial in the size of the input (“NP”) is the same as the class of problems whose solutions can be computed in polynomial time (“P”).  In a series of papers published while at NBS [4], he was the first to describe the complexity class NP, to describe a tractable computation as one that is solvable in polynomial time, and to state the now widely held conjecture that the complexity classes P and NP are not equivalent.  In other words, much of modern computational complexity theory originates from Edmonds' work while at NBS.

References

1. Jack Edmonds, Paths, Trees, and Flowers, Canad. J. Math. 17, 449-467 (1965).
2. Jack Edmonds, Covers and Packings in a Family of Sets, Bull. Amer. Math. Soc. 68, 494-499 (1962).
3. Jack Edmonds, Existence of k-Edge Connected Ordinary Graphs with Prescribed Degrees, J. Res. Natl. Bur. Stand. 68B, 73-74 (1964).
4. Jack Edmonds, Minimum Partition of a Matroid into Independent Subsets, J. Res. Natl. Bur. Stand. 69B, 67-72 (1965).
5. C. Witzgall. Paths, Trees and Flowers. In A Century of Excellence in Measurements, Standards, and Technology (D. R. Lide, ed.), NIST Special Publication 958, 2001. https://nvlpubs.nist.gov/nistpubs/sp958-lide/140-144.pdf

^[1] http://informs.org/

^[2] http://www.claymath.org/millennium/