FS 2025 — Dr. H.-J. Böckenhauer, Prof. Dr. D. Komm, Dr. R. Královič
Algorithmik für schwere Probleme
Inhalt der Vorlesung
Diese Lerneinheit beschäftigt sich mit algorithmischen Ansätzen zur Lösung schwerer Probleme, insbesondere mit parametrisierten Algorithmen und exakten Exponentialzeitalgorithmen.
Termine
Die Vorlesung wird nicht aufgezeichnet.
| Vorlesung | Dienstag | 9‑11 | CAB G 56 | Beginn: 18. Februar 2025 |
| Übungen | Dienstag | 11‑12 | CAB G 56 | Beginn: 25. Februar 2025 |
Vorlesungsinhalt
Der folgende Zeitplan entspricht der vorläufigen Planung und wird im Laufe des Semesters aktualisiert.
Die Kapitelangaben beziehen sich auf das zur Verfügung gestellte Skript.
- 18.02.2025. Allgemeine Einführung, pseudopolynomieller Algorithmus für das Rucksackproblem, starke NP-Schwere. (Abschnitte 4.1, 4.2, 4.4)
- 25.02.2025. Exakte Exponentialzeitalgorithmen: Einführung und Branching-Algorithmen für 3SAT und MAX-IS (Abschnitte 5.1, 5.2)
- 04.03.2025. Exakte Exponentialzeitalgorithmen: Measure-and-Conquer-Methode. (Abschnitt 5.5)
- 11.03.2025. Exakte Exponentialzeitalgorithmen: Inklusion-Exklusion-Prinzip und Set Cover. (Abschnitt 5.4 bis und mit 5.4.1)
- 18.03.2025. Einführung in parametrisierte Algorithmen, Kernbildung, einfache Kernbildung für Vertex-Cover. (Abschnitte 6.1, 6.2.1)
- 25.03.2025. Zusammenhang zwischen Kernbildung und fpt-Algorithmen, Kernbildung für Edge-Clique-Cover, Crown-Decompositions: Definition und Anwendung für Vertex-Cover (Beginn). (Abschnitt 6.2.2, 6.2.3)
- 01.04.2025. Crown-Decompositions: Anwendung für Vertex-Cover (Rest), tiefenbeschränkte Suchbäume (Vertex-Cover und Cluster-Editing). (Abschnitte 6.2.3, 6.3)
- 08.04.2025. Iterative Kompression am Beispiel von Vertex-Cover, Steinerbaum-Problem. (Abschnitte 6.4.1, 6.5)
- 15.04.2025. Baumweite (Einführung und Baumweite spezieller Graphklassen). (Abschnitt 6.6.1)
- 29.04.2025. FPT-Algorithmus für Vertex-Cover bezüglich Baumweite. (Abschnitt 6.6.2)
- 06.05.2025. Grenzen der Parametrisierbarkeit, Schönings Algorithmus für 3SAT. (Abschnitte 6.7 bis und mit Conjecture 6.1, 9.8)
- 13.05.2025. Derandomisierung von Schönings Algorithmus (Überblick). (Abschnitt 9.9.3, bis und mit Lemma 9.6)
- 20.05.2025. Derandomisierung von Schönings Algorithmus. (Abschnitt 9.9.3)
- 27.05.2025. Approximationsalgorithmen. (Abschnitte 7.2, 7.3.4, 7.5.3, 7.6.1)
Prüfungsstoff
Der Prüfungsstoff umfasst alles, was in der Vorlesung behandelt wurde, sowie den Stoff der Übungsblätter und Lösungen.
Skripte
Unter Algorithmics for Hard Problems steht der Entwurf eines noch unveröffentlichen Buches zur Verfügung.
Das Passwort für den Zugriff wird den Teilnehmenden per E-Mail mitgeteilt.
Übungen
Die Übungen werden von Moritz Stocker () betreut. Die Abgaben der Lösungen können per E-Mail an ihn gesendet werden, er steht auch für Fragen zum Inhalt und zur Organisation der Übungen zur Verfügung.
| Datum | Übung | Lösung |
|---|---|---|
| 18.02.2025 | Übungsblatt 1 |
Weiterführende Literatur
- J. Hromkovič: Algorithmics for Hard Problems, 2004, Springer-Verlag, ISBN 3-540-44134-4.
- F. Fomin und D. Kratsch: Exact Exponential Algorithms, 2010, Springer-Verlag, ISBN 978-3-642-16532-0.
- R. Niedermeier: Invitation to Fixed-Parameter Algorithms, 2006, Oxford University Press, ISBN 978-0-19-856607-6.
- M. Cygan et al.: Parameterized Algorithms, 2015, Springer-Verlag, ISBN 978-3-319-21275-3.
- F. Fomin et al.: Kernelization, 2019, Cambridge University Press, ISBN 978-1-107-05776-0.
Kontakt:Moritz Stocker, ; letzte Änderung: ; Haftungsausschluss.