RUB » LMI » Lehre » Seminar zu Approximationsalgorithmen SS 2022

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).