Research Institute for Discrete Mathematics

Lecture Course "Approximation Algorithms"

Summer 2008

In this lecture we introduce the notion of approximation algorithms and present several different techniques for obtaining approximation algorithms for NP-hard problems. We also study the hardness of approximation and will use the PCP-Theorem to prove lower bounds for the approximability of many NP-hard problems.

This lecture requires basic knowledge of combinatorial and linear optimization.

Class Hours: Tuesdays and Thursdays 16:15-17:45
Room: Gerhard-Konow-Hörsaal (in the Arithmeum building, Lennéstr. 2)

Prof. Dr. S. Hougardy