Lecture time:  Wednesday 1012 and Friday, 1214 

Lecture room:  023, Campus E 1.4 
Lecturers:  ChienChung Huang,Rob van Stee 
Tutorial time:  Friday 1718 
Tutorial room:  023, Campus E 1.4 
Tutor:  Fidaa Abed 
Audience: 
The course counts as computer science lecture (6 SWS, 9 CP).
The lecture will be given in English. 
Schedule: 
The first lecture will take place on Tuesday, October 19.

Exercises:  We will hand out exercises every other week. These will count towards your grade. 
Final Exam: 
THURSDAY Feb 10, 12:0014:00, room 023

ReExam:  Thursday Mar 31, 14:0016:00, room 023

Book:  Approximation Algorithms, Vijay Vazirani 
There are many practical problems that cannot be perfectly solved or for which it would take too long to find an optimal solution. An example of such a problem is bin packing, where objects are to be packed in bins and the goal is to use as few bins as possible.
In such cases we have an interest in developing simple algorithms that give `almost' perfect solutions in a reasonable time. Such algorithms are called approximation algorithms. The running time of an approximation algorithm should be polynomial in the size of the input, and the result should not deviate by more than a certain factor from the optimal solution.
There are also many problems in which decisions need to be made without full knowledge of the future or even the present. For instance in the case of bin packing one would like to at some point close some bins and send them away, while new objects may still arrive. Or, when scheduling jobs on machines, one cannot wait until all jobs have arrived before starting to allocate jobs to machine and to run them.
How should one make decisions in such cases?
This is the second central question we consider in this course. We will present online algorithms, that deliver good solutions without knowing the future.
Date  Topic  Reference  Homework  Lecturer 

Oct 19  Introduction  Section 1.1.1, Section 9.0  Huang, van Stee  
Oct 21  Metric Traveling Salesman  Section 3.2  Huang  
Oct 27  Multiway Cut, Kcut  Section 4  Huang  
Oct 28  Set Cover and Application  Section 2.1, Section 2.3  First Assignment  Huang 
Nov 3  Weighted Vertex Cover  Section 2.2  Huang  
Nov 5  Introduction to Linear Programming  Section 14.1, Section 14.3  Huang  
Nov 10  The skiing cow  Assignment 2  van Stee  
Nov 12  Knapsack  Section 8.1, 8.2  Huang  
Nov 17  List Update  van Stee  
Nov 19  Paging  van Stee  
Nov 24  Bin packing  Assignment 3  van Stee  
Nov 26   no class   
Dec 8  Bin packing  van Stee  
Dec 10  Online load balancing  van Stee  
Dec 8  Linear programming  Assignment 4  van Stee  
Dec 10  The primaldual method for online algorithms  van Stee  
Dec 15  Bin Packing  Section 9  Huang  
Dec 17  Minimum Makespan Scheduling  Section 10  Assignment 5  Huang 
Jan 5  Minimum MultiCut  Section 18  Huang  
Jan 7  K Median  This paper  Huang  
Jan 12  Maximum Satisfiability  Section 16  Huang  
Jan 14  Feedback Arc Set  This paper  Huang  
Jan 19  kserver  Assignment 6  van Stee  
Jan 21  kserver  van Stee  
Jan 26  kcenter  van Stee  
Jan 28  kcenter  van Stee  
Feb 2  Maximizing minimum load  van Stee  
Feb 4  Stable marriage  Huang 
Number  Exercises  Final exam  Grade 

2530689  86  32  1.3 
2534438  99  20  2.3 
2535205  119  35  1.0 
2534786  104  28  1.3 