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
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.
