VU Approximation Algorithms

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

- 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