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

Discussion of examples, solving exercises and presenting results in the lecture

ECTS-Breakdown:

21h   lecture time
20h   preparation of homework assignments
  6h   presentation of homework assignments
25h   preparation for final exam
  3h   final exam
-----
75h   total 

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.

knowledge of basic algorithms and data structures, basic proof techniques