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