Approximation Algorithms for Scheduling Problems

(ADM III), SoSe 2010

LV-Nr.: 3236 L 287

Prospective Schedule

Lectures (including exercise sessions):


The field of Approximation Algorithms is among the most active areas of algorithmic research. It combines a rich and deep mathematical theory with the promise of profound practical impact. This field has developed in response to the difficulty in solving NP-hard optimization problems exactly. An approximation algorithm sacrifices optimality in favor of efficient running time together with a provable guarantees on the quality of the computed solution. In this course we give an overview of the field of Approximation Algorithms for scheduling problems and present some of the most important and exciting developments in this area over the past 20 years.


In addition to the usual mathematical basics, good knowledge of linear and combinatorial optimization is required.

Content of lectures and suggested reading

In the following we give a short list of topics covered in each lecture together with pointers to the literature:



We recommend to have a look at some of the books in the following list once in a while (will be updated):

Most of the books are available in the Mathematical Library.

The following articles are also of interest: