|
Vorlesung: Approximationsalgorithmen für NP-harte Probleme
(WS 2003/2004)
Beschreibung:
Viele auch in der Praxis relevante Optimierungsprobleme gehören zur
Klasse der sog. NP-harten Probleme, d.h. man kennt bisher für keines
dieser Probleme einen Algorithmus, der in polynomieller Zeit eine optimale
Lösung berechnet. Eine Möglichkeit zur Behandlung NP-harter Optimierungsprobleme
ist der Verzicht auf eine optimale Lösung. In vielen Fällen können
Algorithmen konstruiert werden, die in polynomieller Zeit eine Näherungslösung
bestimmen, die nachweislich nahe der optimalen Lösung liegt. Die Vorlesung
soll in die Methoden dieses aktuellen Forschungsgebietes der Theoretischen
Informatik bzw. Diskreten Mathematik einführen.
Bereich:
A/C, A1 (Vorlesung mit Übungen, 8 LP)
Termin:
Di, Do 9-11 HS 1
Übungen:
Mi, 14-15 N327
Mi, 17:00-18:30 N1001
Literatur:
- Dorit S. Hochbaum: Approximation Algorithms; Boston, PWS 1997
- Rajeev Motwani, Lecture
Notes on Approximation Algorithms - Volume I
- Ausiello et al.: Complexity and Approximation;; Berlin, Springer 1999
- Vazirani, V.: Approximation Algorithms, Springer 2001
- Viele interessante Artikel (insbesondere zum Thema PCPs) bietet die
Homepage von Sanjeev Arora
|