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)

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

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.