Logbuch Effiziente Algorithmen - Sommer 2026
Vorlesung 8 -- 13.05.2026:
Material:
Benachbarte Ecken, keine lokalen Optima im Lösungspolytop, Umwandlung in Standardform, Ecken in der Standardform, Basis- und Nichtbasiskomponenten und -variablen einer Ecke, Lösungen und Kosten als Funktion einer Basis, Basiswechsel im Simplex-Algorithmus an einer (nicht-entarteten) Ecke. Intuition exponentielle worst-case Laufzeit von Simplex.- Notizen, Abschnitt 3.2
Vorlesung 7 -- 11.05.2026:
Material:
Lineare Programmierung, Beispiele, Umwandlung in kanonische Form, geometrische Interpretation, ungültig/unbeschränkt/beschränkte LPs, Lösungsraum ist konvexes Polyeder/Polytop, Ecken des Polytops, Charakterisierungen, entartete Ecken, eine Ecke des Polytops ist optimale Lösung- Notizen, Abschnitt 3.1.
Vorlesung 6 -- 29.04.2026:
Material:
Maximum Matching in allgemeinen Graphen, augmentierende Pfade, ungerade Kreise, Blüten, Edmonds Algorithmus, Beispiele- Notizen, Abschnitt 2.2.
Vorlesung 5 -- 27.04.2026:
Material:
Varianten von Matching in bipartiten Graphen: Charakterisierung perfekter Matchings, maximum und perfekte Matchings mit minimalen Kosten, Anwendung von Flüssen mit minimalen Kosten, Successive-Shortest-Path Algorithmus mit Nutzung von Knotenpotenzialen und Dijkstra's Algorithmus berechnet ein perfektes Matching mit minimalen Kosten in bipartiten Graphen in Laufzeit O(n3).- Notizen, Abschnitt 2.1 (ab Theorem 5).
Vorlesung 4 -- 22.04.2026:
Material:
Flüsse mit minimalen Kosten, Optimalitätskriterien: (1) Keine Kreise mit negativen Kosten im Restnetzwerk, Cycle-Canceling Algorithmus; (2) Iterative Erhöhung mittels billigster augmentierender Wege, Successive-Shortest-Path Algorithmus. Implemetation mit Dijkstra's Algorithmus, Knotenpotenziale, angepasste Kostenfunktion, Update der Potenziale bei billigsten augmentierenden Wegen.- Notizen, Abschnitt 1.2.
Vorlesung 3 -- 20.04.2026:
Material:
Preflows, Höhenfunktionen, Kompatibilität, PreflowPush Algorithmus, Beispiel. Analyse der Laufzeit über die Anzahl der Relabel Operationen (maximal 2n(n-2)) und der saturierenden Push-Operationen (maximal 2nm). Potenzialfunktion zur Analyse der nicht-saturierenden Push-Operationen (maximal 4n2m).- Notizen, Abschnitt 1.1.2.
Vorlesung 2 -- 15.04.2026:
Material:
Max-Flow-Min-Cut Theorem mit Beweis, Anwendung auf die Berechnung bipartiter Matchings mit größter Kardinalität, Skalierungsvariante mit (schwach) polynomieller Laufzeit von O(m2 log C), Edmonds-Karp-Variante mit stark polynomieller Laufzeit von O(nm2).- Notizen, Abschnitt 1.1.1 (ab Theorem 1) und Abschnitt 2.1.1 (nur Theorem 5).
Vorlesung 1 -- 13.04.2026:
Material:
Organisatorisches, Details zum Übungsbetrieb. Flussprobleme, Definition Flussnetzwerk, Fluss, Wert des Flusses, Restnetzwerk und augmentierende Pfade. Ford-Fulkerson-Algorithmus, Korrektheit, Laufzeit. s-t-Schnitte, Kapazität des Schnittes, Fluss über einen Schnitt, Max-Flow-Min-Cut Theorem.