University of Cologne

Faculty of Mathematics and Natural Sciences
Computer Science Department - Prof. Dr. Michael Jünger


School on Polyhedral Combinatorics

The MINO Initial Training Network of the European Union announces a school for master students and early stage doctoral students of mathematics and computer science:

Jack Edmonds, Professor Emeritus of the University of Waterloo, Canada, teaches

  • Polyhedral Combinatorics,
  • Polytime Combinatorics,
  • Matroids and Submodularity: An overview of some classic subjects

at the

University of Cologne

Monday 16 September - Wednesday 18 September 2013.

This course is free of charge and an exceptional opportunity to experience and get first hand instruction from a great pioneer.

About Jack Edmonds

"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 Alexander 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

 "The view reflected in this book has been founded in large part by the work and vision of Edmonds. […] Basic notions like good characterisation, polynomial algorithms, the polyhedral approach without total unimodularity, polymatroids, and sub modular flows come from his work and form the framework for this entire book." from the book 'Connections in Combinatorial Optimization' by Andras Frank

 "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

The following is as central to the course as NP¬=P : "The conjecture, P = NP ∩ co-NP, also proposed by Edmonds (1965c), is strongly supported by empirical evidence.  Most decision problems which are known to belong to NP intersect co-NP are also known to belong to P." from the book 'Graph Theory' by J.A. Bondy and U.S.R. Murty, 2008



Participation is free of charge and accomodation is not included. We kindly ask you make your own hotel reservation. See below for some recommendations.


Hotels in Cologne can easily be booked via HRS. As a starting point, we have pre-selected some hotels for you:

  • City Class am Dom
  • Central am Dom
  • IBIS Zentrum 
  • IBIS Budget Messe
  • XII Apostel Albergo
  • Am Augustinerplatz
  • Kleines Stapelhäuschen
  • Europäischer Hof am Dom

Additionally, there two A&O hostels in Cologne that offer a central location at a low budget price.

Program and practical information

The school starts on Monday, September 16th, 10:00h and ends on Wednesday, September 18th, 16:00h.

The lectures take place in lecture hall 3 of the physics building. It is located south of the main university building (see here for a map). Access to the building is easiest from the southern side. The building is close to the tram line 9 in the north (exit at Universität and follow the Universitätsstraße in southern direction) and to the tram line 18 in the south (exit at Weißhausstraße and follow the Universitätsstraße in northern direction). In both cases, the walk should be around 5-7 minutes.
If you enter the building through the main entrance (the one on the southern side), follow the hall until you reach an open space with a group of chairs and tables. Turn right just before the open space and you will find the entrance to hall 3 on your left hand side. See here for a map, the lecture room is labeled as "Hörsaal 3" and the main entrance is at the very right of the map.

Course material

The course material is available here.