*Note that this course is cross-listed with the ELTE University and is held on their campus. Its schedule is set by ELTE. Time and location will be available by the beginning of February*

*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.