Forschungsinstitut für Diskrete Mathematik

Vorlesung "Approximationsalgorithmen"

Sommersemester 1998


Da eine exakte Lösung NP-vollständiger Probleme in polynomieller Zeit nicht möglich erscheint, ist man an Approximationsalgorithmen interessiert, die in polynomieller Zeit eine Lösung ermitteln, die bis auf einen a priori garantierten Faktor k optimal ist. Verschiedene Probleme sind unterschiedlich gut approximierbar; z.B. kann k für einige Probleme beliebig nah an 1 gewält werden, für andere ist dies nicht der Fall (es sei denn P=NP). Im Hinblick darauf werden einige klassische kombinatorische Optimierungsprobleme untersucht, unter ihnen das TSP, Knapsack-, Bin-Packing- und Erfüllbarkeitsprobleme.


Vorkenntnisse: Grundbegriffe aus Graphentheorie und Kombinatorischer Optimierung sind hilfreich.
Ort: Hörsaal Lennéstr. 2
Zeit: Dienstags 12-14 Uhr
Beginn: 21.4.1998


J. Vygen