SUBJECT
Title
Polyhedral combinatorics
Type of instruction
lecture + practical
Level
master
Faculty
Part of degree program
Credits
3
Recommended in
Semesters 1-4
Typically offered in
Autumn/Spring semester
Course description
Total dual integrality. Convex hull of matchings. Polymatroid intersection theorem, submodular flows and their applications in graph optimization (Lucchesi-Younger theorem, Nash-Williams’ oritentation theorem).
Readings
- W.J. Cook, W.H. Cunningham, W.R. Pulleybank, and A. Schrijver, Combinatorial Optimization, John Wiley and Sons, 1998.
- B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2000.
- A. Schrijver, Combinatorial Optimization: Polyhedra and efficiency, Springer, 2003. Vol. 24 of the series Algorithms and Combinatorics.