Inhalt

Viele interessante und in der Praxis relevante diskrete Optimierungsprobleme sind NP-schwer. Für sie ist also kein polynomieller Lösungsalgorithmus bekannt und es kann auch kein solcher Algorithmus existieren, außer P=NP. Dennoch besteht ein hoher Bedarf an Verfahren, die mit vertretbarem Rechenaufwand zumindest eine "gute" zulässige Lösung produzieren. Im Unterschied zu Heuristiken, die rein empirisch validiert werden, haben Approximationsalgorithmen eine gewisse Gütegarantie, die sich mathematisch beweisen lässt. Sie sind daher nicht nur oftmals in der Praxis wirksam und verlässlich, sondern auch theoretisch interessant. Im Kurs werden wir verschiedene Approximationsalgorithmen betrachten, Gemeinsamkeiten herausarbeiten und allgemeine Prinzipien zum Entwurf von Approximationsalgorithmen kennen lernen.

Die Veranstaltung wird als sog. Reading Course anhand des Buchs The Design of Approximation Algorithms (frei verfügbar hier) von David P. Williamson und David B. Shmoys angeboten.

Was ist ein Reading Course?

Im diesem "Inverted Classroom"-Format werden die Inhalte gemeinsam im Laufe des Semesters erarbeitet, die Rolle von Snychronveranstaltungen und Einheiten des Selbststudiums sind dabei vertauscht: Die Lektüre des Materials erfolgt zwischen den Treffen unabhängig in vorgegebenen Einheiten und anhand von Leitfragen. Während der wöchentlichen Termine findet dagegen eine interaktive Besprechung des Materials, mit informellen Kurzvorstellungen und der gemeinsamen Bearbeitung kleiner Übungsaufgaben, die auch einen Implementierungsteil umfassen können, statt. Für dieses Format ist es besonders wichtig, dass alle Teilnehmer/-innen dem Lernrhythmus des Kurses folgen. Die Bereitschaft dazu sowie eine regelmäßge aktive Mitatbeit während der wöchentlichen Treffen wird daher vorausgesetzt.

Link zur Veranstaltung im LSF und in moodle.

Termine

• Mo 15:15 - 16:45 online via BigBlueButton
• Di 13:30 - 15:00 online via BigBlueButton

Die zum Betreten des virtuellen Raums benötigten Zugangsdaten wurden allen im LSF für die Vorlesung angemeldeten Teilnehmern kurz vor dem ersten Termin per E-Mail zugeschickt. Für die Nutzung von BigBlueButton ist keine Registrierung oder Installation von spezieller Software notwendig.

Voraussetzungen

Mathematische Grundvorlesungen, Einführung in die Mathematische Optimierung. Weitere Vorkenntnisse in diskreter Optimierung, z.B. aus den Vorlesungen Kombinatorische Optimierung und Ganzzahlige Lineare Optimierung, sind von Vorteil.

Fragen?

Ich freue mich über generelles Interesse und Fragen: