A Lecture and a Course by Jack Edmonds
Rome, May 23-27, 2011

Istituto di Analisi dei Sistemi ed Informatica - Consiglio Nazionale delle Ricerche
Conference Room, viale Manzoni 30 - Roma
Course material:
Recent reprints:
  • Matroid Partition
in the book





  • Submodular Functions, Matroids, and Certain Polyhedra
  • Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems (with R.M. Karp)
  • Matching: A Well-Solved Class of Integer Linear Programs (with E.L. Johnson)
in the book dedicated to Jack
The lecture:

POLYMATROIDS    (Watch the recording of the lecture)

The talk will sketch an introduction to P, NP, coNP, LP duality, matroids, and some other foundations of combinatorial optimization theory.
A predicate, p(x), is a statement with variable input x. It is said to be in NP when, for any x such that p(x) is true, there is, relative to the bit-size of x, an easy proof that p(x) is true. It is said to be in coNP when ¬p(x) is in NP. It is said to be in P when there is an easy (i.e., polynomially bounded time) algorithm for deciding whether or not p(x) is true. Of course P implies NP and coNP.
Fifty years ago I speculated the converse.
Polymatroids are a linear programming construction of abstract matroids. We use them to describe large classes of concrete predicates (i.e., "problems") which turn out to be in NP, in coNP, and indeed in P.
Failures in trying to place the NP "traveling salesman predicate" in coNP, and successes in placing some closely related polymatroidal predicates in both NP and coNP and then in P, prompted me to conjecture that
(1) the NP traveling salesman predicate is not in P, and
(2) all predicates in both NP and coNP are in P.
The conjectures have become popular, and are both used as practical axioms. I might as well conjecture that the conjectures have no proofs.

Monday, May 23 2011, 11:30
Download the poster
The course:

POLYMATROIDS ETCETERA: ALGORITHMS AND PRETTY THEOREMS

A variety of combinatorial existence theorems will be proved by algorithms which tell how to find an instance of what is asserted to exist. Another main purpose will be to introduce polyhedral combinatorics, which uses systems of linear equations to obtain algorithms and theorems. Emphasis will be on matroids and polymatro- ids with a variety of applications, especially to tree systems and branching systems in networks.

Tuesday-Friday, May 24-27 2011, 10:30
Download the poster
If you like to receive reminders or notification of possible schedule changes, please drop your e-mail address into the box below
 


"Pionereed by the work of Jack Edmonds, polyhedral combinatorics
has proved to be a most powerful, coherent and unifying tool
throughout combinatorial optimization. ..."
"Edmonds conjectured that there is no polynomial-time algorithm for the
traveling salesman problem. In language that was developed later, this is
equivalent to NP¬=P."
from the book 'Combinatorial Optimization', by Lex Schrijver

"The classes of problems which are respectively known and not
known to have good algorithms are of great theoretical interest. [...]
I conjecture that there is no good algorithm for the traveling
salesman problem. My reasons are the same as for any mathematical
conjecture: (1) It is a legitimate mathematical possibility, and
(2) I do not know." – Jack Edmonds, 1966
from the book 'Computational Complexity', by Christos Papadimitriou

"Jack Edmonds has been one of the creators of the field
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."

from the citation of the John Von Neumann Theory Prize, 1985
Gallery:

Jack à la Sorbonne

Jack Edmonds is awarded an Honorary Doctorate at the University of Southern Denmark and is congratulated by Queen Margrethe II.

Aussois 2003

Aussois 2008

Jack and some recent PhD's