max planck institut

informatik

informatik

- 05-Feb: The class is over. You can pick your schein from Christina's office.

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 |