Seminar über Approximationsalgorithmen SS 2022
LVR-Nr: | 150 532 |
---|---|
Veranstaltung: | Seminar über Approximationsalgorithmen |
Dozenten: | Maike Buchin, Christoph Ries |
News
- Weitere Informationen zum Seminar werden demnächst per Mail und im Moodle bekannt gegeben.
- Bei Interesse an dem Seminar melden Sie sich bitte per Email bei der Dozentin an.
Kommentar
Viele Optimierungsprobleme, die in der Praxis auftreten, sind NP-schwer, sodass für diese keine polynomiellen Algorithmen bekannt sind. Ein Ansatz, um diese dennoch zu lösen, sind approximative Algorithmen. Dies sind Algorithmen, die nicht zwingend die optimale Lösung finden, aber eine Lösung, die nicht viel schlechter als die optimale Lösung ist. In diesem Seminar betrachten wir Approximationsalgorithmen für eine Reihe klassischer Optimierungsprobleme, wie z.B. dem Travelling Salesman Problem.
Voraussetzungen
Voraussetzung für die Teilnahme am Seminar sind im Bachelor die Vorlesungen Informatik 2 und 3. Teilnehmer im Master sollten noch mindestens eine weitere Vorlesung zu Algorithmen gehört haben, z.B. Effiziente Algorithmen oder Geometrische Algorithmen.
Literatur
Die Seminarthemen orientieren sich an Kapiteln aus den folgenden Büchern "Approximation Algorithms" von Vijay V. Vazirani (Springer, 2001).