Diese Vorlesung beschäftigt sich mit Algorithmen, die NP-schwere Probleme exakt (also optimal) lösen und dafür exponentielle Zeit aufwenden dürfen. Auch wenn es wohl keine exakten Polynomialzeitalgorithmen dafür gibt, wollen wir die Probleme trotzdem in möglichst geringer Zeit und nachweislich optimal lösen. Primär geht es in der Vorlesung um eine Vielzahl algorithmischer Techniken u.a. Branching Algorithmen, Dynamische Programmierung, Inklusion-Exklusion, Measure & Conquer, Subset Convolution und Lokale Suche.Die Vorlesung basiert auf dem gleichnamigen Buch "Exact Exponential Algorithms" von Fedor V. Fomin und Dieter Kratsch. Das Buch kann aus dem Uninetz (oder VPN) über die Unibibliothek beim Verlag heruntergeladen werden.
LV findet auf Englisch statt.
Die Veranstaltung wurde 1 mal im Vorlesungsverzeichnis WiSe 2025/26 gefunden:
