Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage...

- den Unterschied zwischen exakten und approximativen Lösungen zu erläutern
- eigenständig die Approximationsgüte von Algorithmen zu analysieren
- klassische Approximationsresultate für diskrete Optimierungsprobleme zu reproduzieren
- 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

Diskussion von Fallbeispielen, Lösen von Übungsbeispielen und Präsentation in der Vorlesung

ECTS-Breakdown:

21h   Vorlesung
20h   Vorbereitung der Übungsbeispiele
  6h   Präsentation der Übungsbeispiele
25h   Prüfungsvorbereitung
  3h   Prüfung
-----
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.

Kenntnisse über grundlegende Algorithmen und Datenstrukturen, einfache Beweistechniken