A Short Course on Approximation Algorithms by Gerhard Woeginger

(Spring School in Algorithms Geilo, Norway, 1.-4. April 2005)


The talk will survey several basic methods for deriving approximation algorithms for NP-hard problems. The first part deals with linear programming relaxations and how to analyse them. The second part deals with methods for deriving a PTAS/FPTAS. The third part is about methods for negative results (under P not= NP).