Jack Edmonds: the London gigs

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!

with Jack Edmonds

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(AB)+f(AB) ≤ 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.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, exposition and tagged , , , , , , , . Bookmark the permalink.

One Response to Jack Edmonds: the London gigs

  1. I have posted an abstract/advertisement for Jack’s talks at https://cameroncounts.files.wordpress.com/2015/04/edmonds_abstract.pdf

    I have also changed the wording of the post slightly at Jack’s suggestion.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s