FS 2024 — Dr. H.-J. Böckenhauer, Prof. Dr. D. Komm, Dr. M. Wettstein
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: 22. Februar 2024 |
| Übungen | Donnerstag | 14‑15 | CAB G 52 | Beginn: 29. Februar 2024 |
Vorlesungsinhalt
Hier wird der genaue Inhalt der Vorlesung während des Semesters laufend aktualisiert.
Die Quellenangaben im Vorlesungsteil über Approximationsalgorithmen beziehen sich auf die in der Polybox angegebenen Abschnitte des Buches Algorithmics for Hard Problems von J. Hromkovič.
Die Quellenangaben im Vorlesungsteil über Online-Algorithmen beziehen sich auf das unten angegebene Buch An Introduction to Online Computation von D. Komm sowie das unten angegebene Skript von D. Komm.
Einzelne Abschnitte nehmen Bezug auf das unten angegebene Buch The Design of Approximation Algorithms von D. P. Williamson und D. B. Shmoys.
- 22.02.2024. Einführung (Definition 7.1), Approximationsalgorithmen für das metrische TSP: Spannbaumalgorithmus, Christofides-Algorithmus (Abschnitt 7.3.4, bis und mit Theorem 7.5)
- 29.02.2024. 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)
- 07.03.2024. MAX-CUT: Local Search (Abschnitt 7.3.2 bis und mit Theorem 7.2), Randomisierte Approximationsalgorithmen (Definition 9.5), Semi-Definite Relaxierung (Abschnitt 6.1 und 6.2 bis und mit Theorem 6.9 im Buch von Williamson und Shmoys)
- 14.03.2024. Polynomielle Approximationsschemata (PTAS und FPTAS) (Definition 7.3), einfaches (SKP) und allgemeines (KP) Rucksackproblem, Greedy-Algorithmus für SKP (Algorithmus 7.1), PTAS für SKP und KP (Abschnitt 7.5 bis und mit 7.5.2)
- 21.03.2024. Pseudopolynomielle Algorithmen und starke NP-Schwere (Abschnitte 4.1 und 4.4), Dynamische Programmierung für KP (Abschnitt 4.2), FPTAS für KP (Abschnitt 7.5.3), Klassifizierung von Optimierungsproblemen (Abschnitt 7.2)
- 28.03.2024. Einführung Nichtapproximierbarkeit (Abschnitt 7.6 bis und mit Abschnitt 7.6.1), AP-Reduktionen (Abschnitt 7.6.2)
- 11.04.2024. Gap-Probleme und GP-Reduktionen (Abschnitt 7.6.3 bis und mit Observation 7.1), MAX-E3SAT und MAX-2SAT (Lemma 7.7)
- 18.04.2024. 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)
- 25.04.2024. Untere Schranke für die Approximierbarkeit von MAX-3SAT (Theorem 7.14, Korollar 7.15), Unique Games Conjecture (Abschnitt 7.6.5), 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)
- 02.05.2024. 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)
- 16.05.2024. 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), untere Schranke für randomisierte Algorithmen für Paging (Theorem 2.11 im Buch, bzw. Satz 1.18 im Skript)
- 23.05.2024. k-Server-Problem (Abschnitt 4 bis und mit Abschnitt 4.4 im Buch, bzw. Abschnitt 3 im Skript)
- 30.05.2024. Online-Knapsack: Deterministische Algorithmen (Theoreme 6.1 bis 6.3 im Buch, bzw. Sätze 5.2 bis 5.4 im Skript), Advice-Komplexität (Theoreme 6.4 bis 6.7 im Buch, bzw. Sätze 5.5 bis 5.8 im Skript), Randomisierte Algorithmen (Theoreme 6.9 bis 6.12 im Buch, bzw. Sätze 5.10 bis 5.13 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 |
|---|---|---|
| 22.02.2024 | Übungsblatt 1 | Lösung 1 |
| 29.02.2024 | Übungsblatt 2 | Lösung 2 |
| 07.03.2024 | Übungsblatt 3 | Lösung 3 |
| 14.03.2024 | Übungsblatt 4 | Lösung 4 |
| 21.03.2024 | Übungsblatt 5 | Lösung 5 |
| 28.03.2024 | Übungsblatt 6 | Lösung 6 |
| 11.04.2024 | Übungsblatt 7 | Lösung 7 |
| 18.04.2024 | Übungsblatt 8 | Lösung 8 |
| 25.04.2024 | Übungsblatt 9 | Lösung 9 |
| 02.05.2024 | Übungsblatt 10 | Lösung 10 |
| 16.05.2024 | Übungsblatt 11 | Lösung 11 |
| 23.05.2024 | Ü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. Willamson & 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.