Approximationsalgorithmen
Studiengänge
Informatik Bachelor 5. Semester
Angewandte Mathematik Master
Modul 12329 Approximationsalgorithmen
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.

Lehrstuhl Theoretische Informatik
Institut für Informatik