max planck institut
mpii logo Minerva of the Max Planck Society

Optimization II (Winter 09/10)

Announcements [RSS feed]

  • 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
More Courses of the Algorithms and Complexity Group