Research Institute for Discrete Mathematics

Lecture Course "Approximation Algorithms"

Summer 2009

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.

• B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. Springer, 4th edition 2007 (Chapters 16 - 22)
• V.V. Vazirani: Approximation Algorithms. Springer 2001
• S. Arora, C. Lund: Hardness of Approximation. In: Approximation Algorithms for NP-Hard Problems (D.S. Hochbaum, ed.), PWS 1996
• M. Karpinski: Randomisierte und approximative Algorithmen für harte Berechnungsprobleme. Lecture Notes (4th edition), University of Bonn 2000

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