
Dr. Ernst Althaus 
building 46 (MPI), room 308 
Dr. Benjamin Doerr 
building 46 (MPI), room 304 
Lecture  Monday, 9:3011:00 
building 45,
lecture theatre 002 
Lecture  Friday, 13:3015:00 
building 45, lecture theatre 002 
Midterm Exam 
May 30th, 9:1512:15  bulding 45, lectrue theatre 002 
Final Exam 
July 25th, 9:1512:15  bulding 45, lecture theatre 002 
Repeating Exam 
tba  tba 
First lecture 
Friday April 15 
Date  Topic  Reference 
0415  Introduction  [Lee04] Chapter 3 
0418  Theorems of Alternatives (part 1)  [Lee04] Chapter 5 
0422  Theorems of Alternatives (part 2)  [Lee04] Chapter 5 
0425  Duality (part 1)  [Lee04] Chapter 7 
0429  Duality (part 2)  [Lee04] Chapter 7 
0502  Geometry of Linear Programming (part 1)  [BerTsi97] Chapter 2 
0506  Geometry of Linear Programming (part 2)  [BerTsi97] Chapter 2 
0509  Summary and look ahead  
0513  The Simplex Method  [BerTsi97] Chapter 3 
0520  Bland's Rule Finding an initial basic feasible solution  [BerTsi 97] Chapter 3.5 
0523  Implementation of the Simplex Method Dual Simplex Method  [BerTsi97] Chapter 3.3 [BerTsi97] Chapter 4.5 
0527  Sensitivity Analysis  [BerTsi97] Chapter 5 
0530  Midterm Exam  
0603  Ellipsoid Method (part 1)  [BerTsi97] Chapter 8 
0606  Lecture canceled  
0610  Integer linear programming: Introduction Modelling combinatorial problems as ILPs  
0613  Modelling combinatorial problems as ((M)I)LPs: MinMax problems, Boolean expressions, piecewise linear objective functions.  
0617  Unimodularity and Integrality: Main Theorems, 3 examples.  
0620  Unimodularity and Integrality: Applications.  
0627  Ellipsoid Method (part 2)  
0701  Ellipsoid Method (part 2)  
0704  Theorem of Beck and Fiala  
0708  Randomized Rounding  
0711  Hint for the final exam Approximation algorithms  
0715  Approximation algorithms (2) 
Literature for the second half of the lecture: I collected the stuff from different sources, so it is hard to really recommend a reference that helps in preparing for the exam. If you know what I did in the lecture, you are well prepared. For further reading on discrepancy theory, here are some references: