FS 2022 — 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 52 | Beginn: 24. Februar 2022 |
| Übungen | Donnerstag | 14‑15 | CAB G 52 | Beginn: 3. März 2022 |
Vorlesungsinhalt
Hier wird der genaue Inhalt der Vorlesung während des Semesters laufend aktualisiert.
Die Quellenangaben im Vorlesungsteil über Approximationsalgorithmen beziehen sich auf das unten angegebene Buch 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.
- 24.02.2022. Informelle Einführung (Definition 4.2.1.1), Approximationsalgorithmen für das metrische TSP: Spannbaumalgorithmus, Christofides-Algorithmus (Abschnitt 4.3.5 bis vor Aufgabe 4.3.5.6)
- 03.03.2022. Approximationsalgorithmen für Vertex-Cover (Abschnitt 4.3.2 bis und mit Lemma 4.3.2.5), Set-Cover (Skript in Polybox, siehe unten) und gewichtetes Vertex-Cover (Abschnitt 4.3.2 ab dem Text nach Aufgabe 4.3.2.18)
- 10.03.2022. Polynomielle Approximationsschemata (PTAS und FPTAS) (Definition 4.2.1.6), PTAS für das einfache Rucksackproblem (SKP) (Abschnitt 4.3.4 bis und mit Theorem 4.3.4.3), Definition allgemeines Rucksackproblem (KP) und exakter Algorithmus für KP (Abschnitt 3.2.2)
- 17.03.2022. FPTAS für das allgemeine Rucksackproblem (KP) (Abschnitt 4.3.4 ab dem Text nach Theorem 4.3.4.10), Klassifizierung von Optimierungsproblemen nach ihrer Approximierbarkeit (Skript in Polybox, siehe unten), pseudopolynomielle Algorithmen und starke NP-Schwere (Abschnitte 3.2.1 und 3.2.4), Einführung Nichtapproximierbarkeit (Abschnitte 4.4.1 und 4.4.2)
- 24.03.2022. AP-Reduktionen (Abschnitt 4.4.3 bis und mit Lemma 4.4.3.5), Einführung GP-Reduktionen
- 31.03.2022. GP-Reduktionen (Abschnitt 4.4.3 ab dem Text nach Aufgabe 4.4.3.9 ohne Lemma 4.4.3.14)
- 07.04.2022. Probabilistische Verifizierer, das PCP-Theorem und seine Anwendung zum Beweis von Nichtapproximierbarkeit (Abschnitt 4.4.4)
- 14.04.2022. Einführung in Online-Algorithmen (Vorwort und Abschnitt 1.1 bis vor Definition 1.4 im Skript; entspricht ungefähr Abschnitt 1.2 bis und mit Theorem 1.3 im Buch); Definitionen Online-Minimierungsprobleme, Online-Algorithmen und kompetitiver Faktor; das Paging-Problem; FIFO ist (strikt) k-kompetitiv (Skript 1.1)
- 28.04.2022. kein Online-Algorithmus ist besser als k-kompetitiv (Skript 1.2); Randomisierte Online-Algorithmen und erwarteter kompetitiver Faktor (Skript 1.3); der randomisierte Markierungs-Algorithmus ist (strikt) 2Hk-kompetitiv(Skript 1.4)
- 05.05.2022. Einführung untere Schranken für randomisierte Online-Algorithmen; Yaos Prinzip (Lemma 1.13 und Satz 1.15, Skript 1.5); untere Schranke von Hk für die erwarteten Kosten von randomisierten Online-Algorithmen bei Paging (Skript 1.7)
- 12.05.2022. Das k-Server-Problem (Skript 3.0), die k-Server-Vermutung, die randomisierte k-Server, der Greedy-Algorithmus auf der Linie (Skript 3.1), Potentialfunktionen (Skript 3.2), der Double-Coverage-Algorithmus (Skript 3.3)
- 19.05.2022. Einführung in die Advice-Komplexität (Skript 4.0), die Advice-Komplexität von Paging (Skript 4.1, ausser Satz 4.7 alle Sätze ohne Beweise), die Advice-Komplexität von k-Server (Skript 4.2, alle Sätze ohne Beweise)
- 02.06.2022. Das Online-Rucksackproblem (Skript 5.0) und deterministische (Skript 5.1), Advice- (Skript 5.2) und randomisierte (Skript 5.4 und 5.5, ohne die Beweise der Sätze 5.10, 5.11) Algorithmen
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 |
|---|---|---|
| 24.02.2022 | Übungsblatt 1 | Lösung 1 |
| 03.03.2022 | Übungsblatt 2 | Lösung 2 |
| 10.03.2022 | Übungsblatt 3 | Lösung 3 | 17.03.2022 | Übungsblatt 4 | Lösung 4 | 24.03.2022 | Übungsblatt 5 | Lösung 5 |
| 31.03.2022 | Übungsblatt 6 | Lösung 6 |
| 07.04.2022 | Übungsblatt 7 | Lösung 7 |
| 14.04.2022 | Übungsblatt 8 | Lösung 8 |
| 28.04.2022 | Übungsblatt 9 | Lösung 9 |
| 05.05.2022 | ÜbungsBlatt 10 | Lösung 10 |
| 12.05.2022 | ÜbungsBlatt 11 | Lösung 11 |
| 19.05.2022 | Ü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.
Kontakt: Dr. Hans-Joachim Böckenhauer, ; letzte Änderung: ; Haftungsausschluss.