Instructor: Dr. András Frank
Textbook: A. Frank: Connections in Combinaorial Optimization, Oxford Univ. Press (downloadable from the author's website)
Prerequisites:
Polyhedra, polytopes.
Linear Programming duality theorem, Farkas Lemma, Total unimodular
matrices and linear programming. Every bounded polyhedron is the
convex hull of its vertices. Every polytope is a bounded polyhedron
A short description of the course:
Total dual integrality. Convex hull of matchings. Polymatroid
intersection theorem, submodular flows and their applications
in graph optimization (Lucchesi-Younger theorem, Nash-Williams'
orientation theorem).
Further reading:
- 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.