Logbuch Effiziente Algorithmen - Winter 2024/25
Vorlesung 18 -- 10.12.2024:
Material:
Randomisierte Algorithmen, Las-Vegas- und Monte-Carlo-Algorithmen. Minimaler Schnitt, Kontraktionsalgorithmus, Laufzeit O(n2), Erfolgswahrscheinlichkeit Ω(1/n2), Erhöhung durch Wiederholungen. Rekursiver FastCut-Algorithmus, Laufzeit O(n2 log n), Erfolgswahrscheinlichkeit Ω(1/log n)- Notizen, Kapitel 5, Abschnitt 5.1
Vorlesung 17 -- 09.12.2024:
Material:
Steinerbaum und Steinerwald Probleme, ILP für Steinerwald, LP-Relaxierung, primal-dualer Algorithmus, Analogie zu Set Cover. Analyse des Algorithmus mit approximativer dualer Komplementarität, Schranke auf die durchschnittlichen approximativen Faktor für die aktiven Schnitte in jeder Runde, Beweis der 2-Approximation.- Notizen, Abschnitt 4.4.4
Vorlesung 16 -- 03.12.2024:
Material:
Primal-duale Algorithmen, Komplementaritätsbedingungen für optimale Lösungen in primalen und dualen LPs, Schema für primal-duale Algorithmen. Anwendung des Schemas auf das Set Cover Problem, f-Approximtation (f maximale Anzahl Vorkommen eines Elementes in den Mengen). Greedy Algorithmus für Set Cover, Hm-Approximation (m Anzahl Elemente).- Notizen, Abschnitte 4.4.2 und 4.4.3
Vorlesung 15 -- 02.12.2024:
Material:
Vertex Cover auf Bäumen, Linearzeitalgorithmus. Makespan-Scheduling mit allgemeinen Maschinen, parametrisiertes Pruning, Charakterisierung der fraktionalen Ecken-Lösungen als Pseudo-Wälder, Rundung durch vollständiges Matching, 2-Approximation.- Notizen, Abschnitte 4.3.2 und 4.4.1
Vorlesung 14 -- 26.11.2024:
Material:
Gewichtetes k-Center Problem, untere Schranke von 2-ε durch Reduktion von Dominating Set, effizienter Greedy-Algorithmus liefert 2-Approximation. Rucksack Problem, dynamische Programmierung, FPTAS mit Laufzeit O(n3/ε).- Notizen, Abschnitte 4.2.3 und 4.3.1
Vorlesung 13 -- 25.11.2024:
Material:
Travelling-Salesman Problem, allgemeine Nichtapproximierbarkeit, Δ-TSP mit metrischen Kosten, effiziente Approximationsalgorithmen: Spannbaum-Heuristik (2-Approximation), Christofides-Serdyukov Algorithmus (3/2-Approximation).- Notizen, Abschnitt 4.2.2
Vorlesung 12 -- 19.11.2024:
Material:
Makespan-Scheduling auf identischen Maschinen, LPT, Approximationsfaktor 4/3. Definition PTAS und FPTAS, PTAS für konstante Anzahl Maschinen, kein FPTAS für Probleme wie Clique, Independent Set, Vertex Cover. Matching-Heuristik für Vertex Cover ist 2-approximativ, untere Schranken an die Approximierbarkeit von für Vertex Cover, Clique und Independent Set.- Notizen, Abschnitte 4.1.1, 4.1.2 und 4.2.1
Vorlesung 11 -- 18.11.2024:
Material:
Ganzzahlige lineare Programme (ILP), total unimodulare Matrizen, ganzzahlige Optimallösungen eines LPs mit total unimodularer Constraint-Matrix, Anwendungen auf Inzidenzmatrizen und Optimierungsprobleme in Graphen (Max-Flow, kürzeste Wege, Matching und Vertex Cover in bipartiten Graphen). Makespan-Scheduling auf identischen Maschinen, ListScheduling, Approximationsfaktor 2-1/m (untere und obere Schranke).- Notizen, Abschnitte 3.6, 4.1.1
Vorlesung 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.