Summer 2012
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, 5th edition 2012 (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) |
| First Lecture: | Thursday, 5th April |
| Exercise Classes: | Thursday 16:15-17:45, Seminarraum |
Prof. Dr. S. Hougardy