**Summer semester 2023/24**

**Petr Kolman, Hans Raj Tiwary**

**Lectures** take place every week **on Tuesday from 9 am in S8**.
Tutorials take place on Tuesday from 8:15 in S8.

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.

**February 20 (PK)**- Introduction.
- Fourier Motzkin elimination and Farkas lemma.
- Elementary definitions - convex hall, cone, Minkowski sum, H-polyhedron and V-polyhedron.

**February 27 (PK)**- Ellipsoid algorithm, part I - overview, how to start.

**March 5 (PK)**- Ellipsoid algorithm, part II - the iterative step.

**March 12**- Ellipsoid algorithm, part III - when to stop, how to get rid of the simplifying assumptions.

**March 19**- Interior point methods, part I - sketch of the algorithm; potential function; improving direction.

**March 26**- Interior point methods, part II - decrease of the potential in primal steps; dual step.

- 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