Lehrinhalt: Inhaltliche Schwerpunkte:
- kombinatorische Optimierungsprobleme
- Einführung verschiedener Komplexitätsklassen zur Charakterisierung diverser Approximationseigenschaften
- Entwurf verschiedener Approximationsalgorithmen für Probleme wie Travelling Salesman, Bin Packing, Knapsack u.a.
- negative Approximationsresultate, Gap-Technik
- Probabilistically Checkable Proofs PCP, Charakterisierung der Klasse NP durch PCPs
- Negative Approximationsresultate mittels des PCP-Satzes
Literatur:
- Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimizati on Problems and Their Approximability Properties. Springer 1999.
- D. Hochbaum (Hrg.): Approximation Algorithms for NP-Hard Problems PWS Publishing Company, Boston, MA, 1997.
- J. Hromkovic: Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation and Heuristics (Texts in Theoretical Computer Science), Springer 2001.
- V. Vazirani: Approximation Algorithms. Springer 2001.
- R. Wanka: Approximationsalgorithmen, Teubner 2006.
- K. Jansen, M. Markgraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008.
|