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 14:15-15:45|
|Room:||Gerhard-Konow-Hörsaal (in the Arithmeum building, Lennéstr. 2)|
Prof. Dr. S. Hougardy