Der Schwerpunkt der Vorlesung liegt auf der Approximation von
Lösungen NP-harter kombinatorischer Optimierungsprobleme mit Hilfe
randomisierter Algorithmen. Behandelt werden u.a. das Travelling-Salesperson-Problem,
Steinerbäume in Graphen, Mehrgüterflüsse, Packungs- und Überdeckungsprobleme
in Hypergraphen, die Konzentration von Wahrscheinlichkeitsverteilungen um den
Erwartungswert sowie Derandomisierung.
Entwurf und Analyse von Algorithmen für NP-schwere Probleme. Erlernen von Techniken wie Randomisierung, Approximation und Beweis komplexitätstheoretischer Schranken.
Traveling-Salesperson-Problem,
Steinerbäume,
Mehrgüterflüsse,
Large-Deviation-Ungleichungen,
Randomisierte Algorithmen (Randomisiertes Runden),
Packen und Überdecken in Hypergraphen,
Die Random-Hyperplane Methode,
Semidefinite Optimierung,
Max-Cut-Problem,
Flüsse unter spieltheoretischen Aspekten.
Graphentheorie (Inf-GraphTheo) oder Kombinatorische Optimierung - Polynomialität und Optimalität (Inf-KoptPO)
Im ersten Prüfungszeitraum wird eine Klausur geschrieben.
Im zweiten Prüfungszeitraum finden je nach Angemeldetenzahl
mündliche Prüfungen oder eine Klausur statt.
Regelmäßige, angemessene und sinnvolle Bearbeitung von Übungsaufgaben wird bei der Bewertung der Modulprüfung berücksichtigt.
Falls eine Klausur geschrieben wird, so gibt es ein Bonuspunktesystem.
Wenn mindestens 50% aller Übungspunkte bei der Durchführung des Moduls erreicht wurden
und die Klausur alleine