A Short Course on Approximation Algorithms by Gerhard Woeginger
(Spring School in Algorithms
Geilo, Norway, 1.-4. April 2005)
Abstract
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).