Approximation Algorithms

For many important optimization problems we cannot find an optimal solution efficiently. If we want to obtain a solution in a reasonable amount of time, we have to give up optimality and aim for getting a solution with a value as close as possible to the value of an optimal solution. This leads to approximation algorithms which are algorithms that run fast and still give a guarantee on the quality of the solution for any input instance.

The area of approximation algorithms is one of the core areas of modern theoretical computer science. We will discuss approximation algorithms for various classes of problems, including, but not limited to, scheduling, geometric problems and problems on planar graphs. You will learn many important paradigms in the design of approximation algorithms such as LP-rounding, local search, or greedy algorithms. We will also study hardness of approximation, i.e., how one can show that finding a good approximative solution for a problem is NP-hard (and thus as hard as finding the optimal solution).

No previous knowledge of approximation algorithms is required. Please note that you cannot take the exam of this class if you already took the exam of the approximation algorithms class in the summer semester 2014 or in the winter semester 2013/14 (since their contents overlap with this lecture).

In this lecture we use material from the following textbooks

• "Approximation Algorithms" by V. Vazirani (pdf)
• "The Design of Approximation Algorithms" by David P. Williamson and David B. Shmoys (pdf)