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