Approximation Algorithms (ADM III), WS 2010/11

LV-Nr.: 3236 L 287



This handout provides useful information on organizational details of the course. It also contains a tentative schedule of topics covered.


This course will introduce students to the fundamentals in the design and analysis of approximation algorithms. The focus will be on a core set of techniques: greedy algorithms; local search; rounding, scaling, and dynamic progamming; deterministic and randomized rounding of linear programs; semidefinite programming; the primal-dual method; and cuts and metrics.

The course will start with some elementary applications of the techniques to central problems in discrete optimization, and then continue with more recent and advanced applications.


In addition to the usual mathematical basics, good knowledge of combinatorial optimization (ADM I) and linear programming (ADM II) is required.


There will be problem sets, handed out every other week, and a final oral exam for those who request one. The problem set will be due at the beginning of the exercise session in which the answers will be discussed. Students are strongly encouraged to do the problem sets, as this is the best way to learn the course material. Questions from the problem sets may appear on the final oral exam.



The course is based on the book "The Design of Approximation Algorithms" by David P. Williamson and David B. Shmoys (Cambridge University Press, to appear). The book can be obtained as a hard copy from the lecturer or in electronic (unprintable) form on this website. Other materials that might be helpful for the course are listed below.

Most of the books are available in the Mathematical Library.