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

*Sep 21, 2018*