Dr. H.-J. Böckenhauer, Dr. D. Komm — Departement Informatik — FS 2020
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
| Vorlesung | Mittwoch | 13–15 | CAB G 59 | Beginn: 19. Februar 2020 | Übungen | Mittwoch | 15–16 | CAB G 59 | Beginn: 26. Februar 2020 |
Vorlesungsinhalt
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.
- 19.02.2020 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)
- 26.02.2020 Approximationsalgorithmen für Vertex-Cover (Abschnitt 4.3.2 bis und mit Lemma 4.3.2.5), Set-Cover (siehe Skript unten) und gewichtetes Vertex-Cover (Abschnitt 4.3.2 ab dem Text nach Aufgabe 4.3.2.18)
- 04.03.2020 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)
- 11.03.2020 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 (siehe Skript unten), pseudopolynomielle Algorithmen und starke NP-Schwere (Abschnitte 3.2.1 und 3.2.4)
- 18.03.2020 Einführung Nichtapproximierbarkeit (Abschnitte 4.4.1 und 4.4.2), AP-Reduktionen (Abschnitt 4.4.3 bis und mit Lemma 4.4.3.5)
- 25.03.2020 GP-Reduktionen (Rest von Abschnitt 4.4.3 ab dem Text nach Aufgabe 4.4.3.9 ohne Lemma 4.4.3.14)
- 01.04.2020 Probabilistische Verifizierer, das PCP-Theorem und seine Anwendung zum Beweis von Nichtapproximierbarkeit (Abschnitt 4.4.4)
- 08.04.2020 Unique-Games-Conjecture und Zusammenhang mit Nichtapproximierbarkeit (siehe Skript unten); 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)
- 23.04.2020 Definitionen Online-Minimierungsprobleme, Online-Algorithmen und kompetitiver Faktor; das Paging-Problem; FIFO ist (strikt) k-kompetitiv (Skript 1.1); kein Online-Algorithmus ist besser als k-kompetitiv (Skript 1.2)
- 29.04.2020 Randomisierte Online-Algorithmen und erwarteter kompetitiver Faktor (Skript 1.3); der randomisierte Markierungs-Algorithmus ist (strikt) Hk-kompetitiv(Skript 1.4)
- 06.05.2020 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)
- 13.05.2020 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)
- 20.05.2020 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)
- 27.05.2020 Advice und Randomisierung (Skript 6.0), das Online-Rucksackproblem (Skript 5.0) und deterministische (Skript 5.1), Advice- (Skript 5.2, ohne den Beweis von Satz 5.8) und randomisierte (Skript 5.4, ohne die Beweis 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
Hier gibt es Links zu Skripten für Themen der Vorlesung, die in dieser Form nicht in der angegebenen Literatur enthalten sind.
- Analyse des Greedy-Set-Cover-Algorithmus
- Klasseneinteilung von Optimierungsproblemen
- Die Unique-Games-Conjecture
Übungen
| Datum | Übung | Lösung |
|---|---|---|
| 19.02.2020 | Übungsblatt 1 | Lösung 1 |
| 26.02.2020 | Übungsblatt 2 | Lösung 2 |
| 04.03.2020 | Übungsblatt 3 | Lösung 3 |
| 11.03.2020 | Übungsblatt 4 | Lösung 4 |
| 18.03.2020 | Übungsblatt 5 | Lösung 5 |
| 25.03.2020 | Übungsblatt 6 | Lösung 6 |
| 01.04.2020 | Übungsblatt 7 | Lösung 7 |
| 08.04.2020 | Übungsblatt 8 | Lösung 8 |
| 22.04.2020 | Übungsblatt 9 | Lösung 9 |
| 29.04.2020 | Übungsblatt 10 | Lösung 10 |
| 06.05.2020 | Übungsblatt 11 | Lösung 11 |
| 13.05.2020 | Übungsblatt 12 | Lösung 12 |
| 20.05.2020 | Übungsblatt 13 | Lösung 13 |
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. Dennis Komm, , Haftungsausschluss, letzte Änderung: 28.05.2020 13:50.