Logbuch Effiziente Algorithmen - Winter 2024/25
Lecture 10 -- 05.11.2024:
Material:
Schwache und starke Dualität. Größe der Darstellung eines LPs und einer optimalen Lösung, Interior-Point Verfahren, Skalierung, Potenzialfunktion, primale und duale Schritte, polynomielle Laufzeit ohne Beweis.- Notizen, Abschnitte 3.4, 3.5
Vorlesung 9 -- 04.11.2024:
Material:
Seidels LP Algorithmus, Beispiel, Korrektheit, Beweis der Laufzeit O(n! m). Dualität für lineare Programme in kanonischer Form, Herleitung über die Beschränkung des optimalen Wertes der Zielfunktion, "Rezept" zur Erstellung des Dualen, Beispiele.- Notizen, Abschnitte 3.3, 3.4
Vorlesung 8 -- 29.10.2024:
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. Zweiphasenalgorithmus zur Bestimmung von ungültigen LPs. Intuition exponentielle worst-case Laufzeit von Simplex. Idee Seidels Algorithmus.- Notizen, Abschnitte 3.2, 3.3
Vorlesung 7 -- 28.10.2024:
Material:
Lineare Programmierung, Beispiele, Umwandlung in kanonische Form, geometrische Interpretation, ung¨tig/unbeschränkt/beschränkte LPs, Lösungsraum is konvexes Polyeder, Ecken des Polytops, Charakterisierungen, entartete Ecken, eine Ecke des Polytops ist optimale Lösung- Notizen, Abschnitt 3.1.
Vorlesung 6 -- 22.10.2024:
Material:
Bipartites Matching mit maximalen Gewicht. Maximum Matching in allgemeinen Graphen, augmentierende Pfade, ungerade Kreise, Blüten, Edmonds Algorithmus- Notizen, Abschnitte 2.1 und 2.2.
Vorlesung 5 -- 21.10.2024:
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 -- 15.10.2024:
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 -- 14.10.2024:
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 -- 08.10.2024:
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 -- 07.10.2024:
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.