|
Vorlesung: Approximationsalgorithmen für NP-harte Probleme
(WS 08/09)
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,
d°ie 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, 4 LP)
Termin:
Mi 9-11 HS 1
Übungen:
n.Vereinb.
Skript
|