FS 2026 — Dr. H.-J. Böckenhauer, Prof. Dr. D. Komm
Approximations- und Online-Algorithmen
Inhalt der Vorlesung
Diese Lerneinheit behandelt approximative Verfahren für schwere Optimierungsprobleme und algorithmische Ansätze zur Lösung von Online-Problemen sowie die Grenzen dieser Ansätze.
Termine
Die Vorlesung wird nicht aufgezeichnet.
| Vorlesung | Donnerstag | 10‑12 | CAB G 59 | Beginn: 19. Februar 2026 |
| Übungen | Donnerstag | 14‑15 | CAB G 52 | Beginn: 26. Februar 2026 |
Vorlesungsinhalt
Hier wird der genaue Inhalt der Vorlesung während des Semesters laufend aktualisiert.
Die Quellenangaben im Vorlesungsteil über Approximationsalgorithmen beziehen sich auf die angegebenen Abschnitte der überarbeiteten (noch nicht veröffentlichten) Version des Buches Algorithmics for Hard Problems von J. Hromkovič, die in der Vorlesung zur Verfügung gestellt wird.
Die Quellenangaben im Vorlesungsteil über Online-Algorithmen beziehen sich auf das unten angegebene Buch An Introduction to Online Computation von D. Komm.
- 19.02.2026. Einführung (Definition 7.1), Approximationsalgorithmen für das metrische TSP: Spannbaumalgorithmus, Christofides-Algorithmus (Abschnitt 7.3.4, bis und mit Theorem 7.5)
- 26.02.2026. Approximationsalgorithmen für Vertex Cover (Abschnitt 7.3.1, bis und mit Theorem 7.1), gewichtetes Vertex Cover (Abschnitt 10.3 (Definition), Abschnitt 10.5 bis und mit Theorem 10.1) und Set Cover (Abschnitt 7.4.2)
- 05.03.2026. Polynomielle Approximationsschemata (PTAS und FPTAS) (Definition 7.3), einfaches (SKP) und allgemeines (KP) Rucksackproblem, Greedy-Algorithmus für SKP (Algorithmus 7.1), PTAS und FPTAS für SKP und KP (Abschnitt 7.5)
- 12.03.2026. Klassifizierung von Optimierungsproblemen (Abschnitt 7.2), starke NP-Schwere (Abschnitt 4.4), Einführung Nichtapproximierbarkeit (Abschnitt 7.6 bis und mit Abschnitt 7.6.1), AP-Reduktionen (Abschnitt 7.6.2 bis vor Def. 7.12)
- 19.03.2026. Gap-Probleme und GP-Reduktionen (Abschnitt 7.6.3 bis und mit Observation 7.1), MAX-E3SAT und MAX-2SAT (Lemma 7.7)
- 26.03.2026. GP-Reduktion von MAX-CL auf MAX-CL (Lemma 7.8), Probabilistische Beweisverifikation und das PCP-Theorem (Abschnitt 7.6.4 bis und mit Theorem 7.13)
- 02.04.2026. Untere Schranke für die Approximierbarkeit von MAX-3SAT (Theorem 7.14, Korollar 7.6), Unique Games Conjecture (Abschnitt 7.6.5), Approximationsalgorithmus für MAX-CUT (Abschnitt 7.3.2)
- 16.04.2026. Einführung Online-Algorithmen und Kompetitivität (Definitionen 1.4, 1.5 und 1.6 im Buch, bzw. Definitionen 1.1, 1.2 und 1.3 im Skript), Paging-Problem: Untere Schranke für deterministische Algorithmen, Kompetitivität von FIFO, Nicht-Kompetitivität von LIFO (Abschnitt 1.3 und Abschnitt 1.4 bis und mit Theorem 1.6 im Buch, bzw. Satz. 1.5 und Abschnitt 1.2 im Skript), randomisierter Marking-Algorithmus (Definitionen 2.1 und 2.2, sowie Theorem 2.2 im Buch, bzw. Definitionen 1.7 und 1.8, sowie Abschnitt 1.4 im Skript)
- 23.04.2026. Kompetitivität des randomisierten Marking-Algorithmus (Theorem 2.2 im Buch, bzw. Satz 1.12 im Skript), Yaos Prinzip (Abschnitt 2.3.1 im Buch, bzw. Abschnitt 1.5 im Skript)
- 30.04.2026. Untere Schranke für randomisierte Paging-Algorithmen (Theorem 2.11 im Buch, bzw. Satz 1.18 im Skript), Einführung k-Server-Problem (Abschnitte 4.1 bis 4.3 im Buch, bzw. Abschnitte 3.1 und 3.2 im Skript)
- 07.05.2026. Einführung Advice-Komplexität (Abschnitt 3.1 im Buch, bzw. Abschnitt 4 bis Satz 4.3 im Skript), Online-Knapsack: Deterministische Algorithmen und Advice-Komplexität (Abschnitte 6.1 bis 6.3 im Buch, bzw. Sätze 5.1 bis 5.3 im Skript), Barely-Random-Algorithmus (Abschnitt 6.4.1 im Buch, bzw. 5.4 im Skript)
- 21.05.2026. k-Server-Problem auf der Linie (Abschnitt 4.3 und 4.4 im Buch, bzw. 3.2 und 3.3 im Skript), k-Server auf der Linie mit Advice (Theorem 4.11 im Buch)
- 28.05.2026. Advice-Komplexität von Paging (Abschnitt 3.4 im Buch, bzw. Abschnitt 4.1 im Skript, ohne Beweis von Theorem 3.5, bzw. Satz 4.4), k-Server mit Advice (Abschnitt 4.6.1 im Buch, bzw. Abschnitt 4.2 im Skript ohne formale Beweise), Zusammenhang zwischen Randomisierung und Advice (Theorem 3.7 im Buch, bzw. Satz 6.1 im Skript)
Prüfungsstoff
Der Prüfungsstoff umfasst alles, was in der Vorlesung behandelt wurde, sowie den Stoff der Übungsblätter und Lösungen.
Skripte
Materialien wie Skripte für Themen der Vorlesung, die in dieser Form nicht in der angegebenen Literatur enthalten sind, sind hier zu finden: Polybox. Das Passwort für den Zugriff wird per E-Mail mitgeteilt.
Übungen
| Datum | Übung | Lösung |
|---|---|---|
| 19.02.2026 | Übungsblatt 1 | Lösung 1 |
| 26.02.2026 | Übungsblatt 2 (am 05.03. angepasst) | Lösung 2 |
| 05.03.2026 | Übungsblatt 3 | Lösung 3 |
| 12.03.2026 | Übungsblatt 4 | Lösung 4 |
| 19.03.2026 | Übungsblatt 5 | Lösung 5 |
| 28.03.2026 | Übungsblatt 6 | Lösung 6 |
| 02.04.2026 | Übungsblatt 7 | Lösung 7 |
| 16.04.2026 | Übungsblatt 8 | Lösung 8 |
| 23.04.2026 | Übungsblatt 9 | Lösung 9 |
| 30.04.2026 | Übungsblatt 10 | Lösung 10 |
| 07.05.2026 | Übungsblatt 11 | Lösung 11 |
| 21.05.2026 | Übungsblatt 12 | Lösung 12 |
Literatur
- J. Hromkovič: Algorithmics for Hard Problems, 2004, Springer-Verlag, ISBN: 3-540-44134-4.
- D. Komm: An Introduction to Online Computation: Determinism, Randomization, Advice, 2016, Springer-Verlag, ISBN: 3-319-42747-4; ein Skript, das Teile des Buchs enthält, ist online verfügbar.
- D. P. Williamson & D. B. Shmoys: The Design of Approximation Algorithms, 2011, Cambridge University Press, ISBN: 978-0-521-19527-0.
Kontakt: Dr. Hans-Joachim Böckenhauer, ; letzte Änderung: ; Haftungsausschluss.