Mathematical Programming and Polyhedral Combinatorics

Mathematical Programming and Polyhedral Combinatorics, NOPT034

Winter semester 2020/21

Petr Kolman, Martin Loebl

The weekly lecture takes place every Monday from 14:00 - 15:30 pm, on Zoom. The first half of the lecture was taught by prof. M. Loebl. From November 23, we are going to meet on Zoom, Meeting ID: 912 5331 5573, Passcode: matprog.

Exam

The exam consists of two parts. The first part covers the material presented by Martin Loebl (matroids etc.) is examined by him, the second part covers the material covered by me (the ellipsoid and interior point algorithms). Please let me know when you would like to take the second part of the exam and we will agree on the date.

Covered topics (by Petr Kolman)

November 23 notes
- Introduction, Ellipsoid algorithm - part I (How to start).
November 30 notes video
- Ellipsoid algorithm, part II (The Iterative step).
December 7 notes video
- Ellipsoid algorithm, part III (The Iterative step, contd., When to stop).
December 14 notes video
- Interior point methods, introduction.
December 21 notes video
- Interior point methods, part II (Decrease of the potential in primal steps; dual step).
January 4, 2021 notes video
- Interior point methods, part III (Decrease of the potential in dual steps; finding the initial pair of strictly feasible solutions).

Tentative Syllabus

Matroids
Submodular functions and invitation to algorithmic game theory
Ellipsoid algorithm for linear programming
Interior point methods for linear programming

Course Credit

You can either do a project in algorithmic game theory (contact Martin Loebl for details), or a project in linear programming - check the details.

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

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

Jan 4, 2021