Universität Bonn

Institut für Informatik V

Prof. Dr. N. Blum

Vorlesung: Approximationsalgorithmen für NP-harte Probleme
(WS 1999/2000)

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. Disketen Mathematik einführen.