- Verständnis für die Begriffe von exakten und approximativen Lösungen
- Fähigkeit zur eigenständigen Analyse von Approximationsgüten
- Kenntnis von klassischen Approximationsresultaten für diskrete Optimierungsprobleme
- Fähigkeit Publikationen über Approximationsalgorithmen zu verstehen

- Qualitätsmaße von Approximationsalgorithmen
- Schemata von Heuristiken und Methoden der Approximationsabschätzung
- Heuristiken und ihre Analyse für Bin Packing, Scheduling, Knapsack, TSP, Vertex Cover und Set Cover Probleme

ECTS-Breakdown:

21h   Vorlesung
20h   Vorbereitung der Übungsbeispiele
  6h   Präsentation der Übungsbeispiele
25h   Prüfungsvorbereitung
  3h   Prüfung
-----
75h   total 

- Drei Übungsblätter mit Kreuzelliste
- aktive Mitarbeiter in der LV
- mündliche Prüfung (ca. 20 Minuten) nach Abschluss der LV.

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.

Kenntnisse über grundlegende Algorithmen und Datenstrukturen, einfache Beweistechniken