Seminar Optimierung

Henning Bruhn-Fujimoto und Laura Gellert

Bei einer Vielzahl von Optimierungsproblemen stellt sich heraus, dass sie zwar aus theoretischer Sicht als schwer gelten müssten, in der Praxis jedoch effizient lösbar sind. Oftmals liegt dies an der eher speziellen Struktur der Eingaben, die in der Praxis auftreten. Zum Beispiel mögen diese Eingaben eher "dünn" sein, in dem Sinne, dass es eher wenige Abhängigkeiten innerhalb der Daten gibt.

In diesem Seminar wird eine Technik betrachtet, die eine eventuelle "Dünnheit" der Eingaben auf systematische Weise ausnutzt, um das gegebene Optimierungsproblem mittels dynamischer Programmierung zu lösen. Ein zentrales Maß für Dünnheit ist dabei die Baumweite. Desweiteren werden wir einen erstaunlichen Zusammenhang zur Logik beleuchten (Courcelle's theorem, monadic second order logic).


Voraussetzungen: Optimierung und/oder Graphentheorie nützlich, jedoch nicht zwingend erforderlich.


Provisorischer Zeitpunkt: dienstags 10h-12h (bei Terminüberschneidungen werden wir individuelle Lösungen finden)

Themen

  1. Einführung (28. April, E60 HeHo 18, Henning Bruhn & Laura Gellert)

  2. Definition von Baumzerlegungen und Baumweite (5. Mai, E60 HeHo 18, Fabrice Bacquele)
    Literatur

  3. Dynamische Programmierung in Bäumen und series-parallel graphs (19. Mai, E60 HeHo 18, Jonas Klesel)
    Algorithmen für Max Independent Set, evtl. Domination
    Literatur

  4. Dynamische Programmierung bei beschränkter Baumweite (26. Mai, E60 HeHo 18, Miriam Eicher-Abel)
    Algorithmen für Max Independent Set und Färbung
    Literatur

  5. Approximation von Wegbreite (2. Juni, E18 HeHo 22, Axel Dieing)
    Literatur

  6. Monadic Second Order Logic und Courcelles Satz (9. Juni, E60 HeHo 18, Christian Meyer)
    Definition MSO, Darstellung von Optimierungsproblemen in MSO, Bedeutung von Courcelles Satz
    Literatur

  7. Clique width, MSO1 und Courcelles Satz (16. Juni, E18 HeHo 22, Dragan Ströbele)
    Definition clique width, MSO1 vs MSO2, Anwendung für Co-Graphen
    Literatur

  8. Model-Checking auf gelabelten Bäumen und Skizze des Beweises von Courcelles Satz (23. Juni, N25/2101)
    Reduktion des Ursprungsproblems auf das Model-Checking-Problem für MSO auf gelabelten Bäumen, Einführung in das Model-Checking auf Bäumen
    Literatur