Jack Edmonds is a larger-than-life figure in the world of combinatorial optimization and polyhedral combinatorics. If you are a student, you really should grasp this chance to meet him!
More than fifty years ago, Jack was perhaps the first person to make a clear distinction of “easy” (polynomial time) and “hard” problems, and “easily certifiable” answers, now formalised as P and NP. The concepts of P, NP, and co-NP together with discussion and conjectures are clear in Jack’s papers from the mid-1960s, including the conjecture that there is no polynomial time algorithm for the travelling salesman problem (TSP).
In the early 1970s, Stephen Cook, Leonid Levin, and Richard Karp, showed that various familiar NP problems, including the TSP, are as hard as any NP problem, that is, “NP-complete”. Since then, using the assumption of the non-easiness of TSP, that is, NP ≠ P, and trying to prove or disprove it, have become a staple of the fields of combinatorial optimization and computational complexity.
Jack is known for many other important results such as the “blossom algorithm” for maximum matching, the matroid intersection theorem, “the greedy algorithm”, theory of polymatroids and submodularity (f(A∪B)+f(A∩B) ≤ f(A)+f(B)), and much more. He is still creative, with recent work on Euler complexes and Nash equilibria among other things, and he loves to perform.
So I am delighted to have had a small part in setting up two short courses by Jack in London in June, aimed at students:
- At Queen Mary, University of London, 16-19 June: Combinatorial structure of paths, network flows, marriage, routes for Chinese postmen, traveling salesmen, and itinerant preachers, optimum systems of trees and branchings. (Contact: Alex Fink)
- At the London Taught Course Centre, 22-23 June (an LTCC Intensive): Combinatorial structure of submodularity, matroids, learning, transferable & other n-person games, bimatrix games and Nash equilibria. (Contact: Nisha Jones)
Further details will be available from the web page.