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