**Summer semester 2022/23**

**Petr Kolman, Hans Raj Tiwary**

The scheduling of the lectures will be decided at the beginning of the semester; you can affect the scheduling by participating in the voting.

**Lectures** take place every week **on Friday from 9 am in S6**.

In the first part of the lecture, we will cover basics of the theory of polytopes such as the Minkowski-Weyl theorem, face-lattice, 1-skeleton, etc. In the second part we describe in detail the ellipsoid algorithm and the interior point methods (IPMs). It is worth mentioning that the framework of IPMs is a key ingredient of the recent algorithm for exact maximum flow in almost linear time.

- Polyhedra/Polytopes: basic notions, face lattice, polar duality
- Ellipsoid algorithm for linear programming
- Interior point methods for linear programming
- Extended formulations

- Textbook Lectures on Polytopes by Guenter M. Ziegler - available in the University library at Mala Strana.
- 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)

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