Mathematical Programming and Polyhedral Combinatorics, NOPT034

Petr Kolman, Martin Loebl

Tentative Syllabus

• Matroids
• Submodular functions and invitation to algorithmic game theory
• Ellipsoid algorithm for linear programming
• Interior point methods for linear programming

Textbooks, Lecture Notes

Lecture notes on the ellipsoid algorithm by M. Goemans
Lecture notes on interior point method by M. Goemans (see chapter 13)
Textbook Linear Programming by Howard Karloff, chapters 4 and 5 - available in the University library at Mala Strana. Lecture notes on polynomial time LP algorithms by P. Kolman (in Czech)

Other courses on Combinatorial Optimization

• Combinatorial Optimization by Michel Goemans at MIT
• Linear and Semidefinite Programming by Anupam Gupta and Ryan O'Donnell at CMU