Mathematical Programming and Polyhedral Combinatorics, NOPT034

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.

Tentative Syllabus

This is a master-level course focusing on two topics in combinatorial optimization: i) structure of polytopes and the complexity of their description, ii) efficient methods for optimization over polytopes (and polyhedra).

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.

Tentative Syllabus

Textbooks, Lecture Notes

Other courses on Combinatorial Optimization

February 13, 2023