- Understanding the basic terms of exact and approximative solutions
- Being able to analyze approximation ratios
- Knowing classical approximability results for discrete optimization problems
- Being able to 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

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 

- Three exercise sheets
- active participation
- oral exam (approx. 20 Min.) after completion of the course.

Anmeldung zur LVA

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