max planck institut
informatik
informatik
| Lecture time: | Monday 10:00-12:00 |
|---|---|
| Lecture room: | 024, Campus E 14 |
| Lecturers: | Khaled Elbassioni and Julián Mestre |
| Tutorial time: | Thursday 18:00-19:00 |
| Tutorial room: | 024, Campus E 14 |
| Tutor: | Imran Rauf |
This class is the follow-up to Optimization I, which is regularly offered during the Summer term. It is, however, not necessary to haven taken Optimization I in order to take Optimization II. This class will focus mostly on applications of linear programming rather than on how to solve linear programs. We will cover a range of topics, such as: Totally unimodular matrices, uncrossing arguments and their application to optimization, fast algorithms for network flow, matching problems, and covering/packing LPs, Hirsch conjecture, approximation algorithms.
| Date | Topic | Notes | Homework | Lecturer |
|---|---|---|---|---|
| Oct 12 | Maximum weight matching via auctions | LN 1 | HW 1 | Julian |
| Oct 19 | An approximation algorithm for matrix games | LN 2 | HW 2 | Khaled |
| Oct 26 | Push-relabel: The generic algorithm | LN 3 | Julian | |
| Nov 2 | Push-relabel: implementation and highest-label rule | LN 4 | HW 3 | Julian |
| Nov 9 | Multiplicative weight update | LN 5 | HW 4 | Khaled |
| Nov 16 | Fast approximation algorithms for LP solving | LN 6 | Khaled | |
| Nov 23 | Packing and covering LPs | LN 7 | HW 5 | Khaled |
| Nov 30 | Multi-commodity flows Online packing and covering |
BN (Ch4) | Khaled | |
| Dec 7 | Midterm | Julian | ||
| Jan 4 | Balanced matrices | LN 9 | HW 6 | Julian |
| Jan 11 | Matroid and matroid intersection | LN 10 | HW 7 | Julian |
| Jan 18 | Minimum degree-constrained spanning tree | LN 11 | HW 8 | Julian |
| Jan 25 | Solving the spanning tree LP | LN 12 | Julian |
This is a 6-credit-point course. There will be homeworks due every other week. Homework scores do not count towards you final grade, but you need to collect at least 50% of the homework points to be eligible to take the exams. There will be a midterm and a final exam. Your final grade will be the average of these two exams. You can improve your grade by taking an oral re-exam. In order words, you grade will be max((M+F)/2,R). If you want you can also do a project, in which case your grade will be max((M+F+P-min(M,F,P))/2,R). The exams will be on the following dates:
| Midterm: | December 7 |
|---|---|
| Final: | February 1 |
| Re-exam: | March 22 |