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.
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).
Tentative Syllabus
Textbooks, Lecture Notes
Other courses on Combinatorial Optimization
February 13, 2023