After successful completion of the course, students are able to...

- explain the difference between exact and approximative solutions

- analyze the approximation ratios of algorithms

- reproduce classical approximability results for discrete optimization problems

- understand published articles in the area of approximation algorithms

- Measure of quality for approximation algorithms

- Basic schemes of heuristics and methods to determine the approximation ratio

- Heuristics and their analysis for Bin Packing, Scheduling, Knapsack, TSP, Vertex Cover and Set Cover Probleme

After a successful completion of the course, students are able to understand the complexity respectively the approximability status of discrete optimization problems. Moreover, they have the theoretical basics for doing a worst-case analysis for a given approximation algorithm.

K. Jansen, M. Margraf, Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008.

R. Wanka, Approximationsalgorithmen: Eine Einführung, Teubner, 2006.

D.S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Company, 1997.

V.V. Vazirani, Approximation Algorithms, Springer, 2001.

G. Ausiello et al., Complexity & Approximation, Springer, 1999.