Online- und Approximationsalgorithmen

Worum geht's

Du lernst Grundlagen und fortgeschrittene Techniken der Online- und Approximationsalgorithmen. Am Ende kennst du klassische Online-Probleme (z. B. Scheduling, Paging, k-Server), Analysewerkzeuge wie amortisierte Analyse und randomisierte Algorithmen sowie Entwurfstechniken für Approximationsalgorithmen inklusive LP-Relaxierung und randomisiertes Runden.

Was du danach kannst

• Kenntnis grundlegender Online-Probleme in Ressourcenverwaltung, Datenstrukturen und Scheduling
• Verstehen und Anwenden der amortisierten Analyse
• Vertrautheit mit randomisierten Online-Algorithmen und Gegnerkonzept
• Kenntnis zentraler Approximationsalgorithmen für Max-Cut, TSP und Lastbalancierung
• Entwurf und Analyse polynomialer Approximationsschemata (z. B. Rucksack, Lastbalancierung)
• Anwenden von LP-Relaxierung und randomisiertem Runden
• Approximationstechniken für Set-Cover und Shortest-Superstring

Aus was das Modul besteht

• VorlesungVermittlung der theoretischen Inhalte im Vortrag und durch Präsentation
• ÜbungBearbeitung und Besprechung von Übungsblättern zur Vertiefung und individuellen Rückmeldung

Lehrmethode

• Vortrag/Präsentationzur strukturierten Vermittlung der Vorlesungsinhalte
• Übungsblätter mit Korrekturzur inhaltlichen Auseinandersetzung und individuellen Rückmeldung über Lernfortschritt
• Übungsbesprechungzur gemeinsamen Lösung und Klärung offener Fragen