Vorlesungen

1. Mittwoch, 9. April 2014 (pdf)
TEIL I: KOMBINATORISCHE GRAPHEN-ALGORITHMEN
Kapitel 1 Einführung: Stabile Matchings
1.1 Grundbegriffe
Def: Matching
Interpretation als Massenhochzeit
Def: Stabiles Matching
Naiver Algorithmus mit Laufzeit n!
1.2 GaleShapley Algorithmus
Algorithmus
Beispiel
Satz: Gale-Shapley Algorithmus berechnet stabiles Matching. Insbesondere gibt es immer eines.
2. Freitag, 11. April 2014 (pdf)
Bem: Nur $n^2$ Heiratsanträge im Gale-Shapley Algorithmus.
Satz: Der Gale-Shapley Algorithmus berechnet das für die Männer beste stabile Matching
1.3 Geometrische Modellierung
Vor- und Nachteile kombinatorischer Algorithmen
Vor- und Nachteile geometrischer Modellierung mit linearen Ungleichungen
Codierung von stabilen Matchings mit Hilfe von Permutationsmatrizen
Satz: Charakterisierung von stabilen Matchings mit linearen Ungleichungen
Ausblick: Lineare Optimierung über das Stabile Matching Polytop
Kapitel 2 Kürzeste Wege
2.1 Nichtnegative Kantenlängen
Notation: gerichteter Graph, Knoten, gerichtete Kanten, Kantenlängen, Kantenfolge,
s-t-Weg, Abstand, s-t-Schnitt
Satz: min-max Charakterisierung kürzester Weg
3. Mittwoch, 16. April 2014 (pdf)
Satz: min-max Charakterisierung kürzester Weg
2.2 Beliebige Kantenlängen
Bsp: Rucksackproblem
Algorithmus von Bellman-Ford
Satz: $d_k($v$) = \min\{l(P) : P$ ist s-v-Kantenfolge mit $\leq k$ Kanten$\}$
Def: gerichteter Kreis
Satz: Existenz kürzester s-t-Kantenfolgen, die Wege sind, falls Graph keine Kreise negativer Länge enthält
4. Mittwoch, 23. April 2014 (pdf)
Bemerkungen zu Algorithmus von Bellman-Ford
Satz: $d_n = d_{n-1}$ genau dann, wenn alle von s aus erreichbaren gerichteten Kreise nicht-negative Länge haben
2.3 Geometrische Modellierung, Potentiale
Def: Potential
Satz: Es existiert ein Potential genau dann, wenn alle gerichteten Kreise nicht-negative  Länge haben
Satz: geometrische Modellierung kürzester Wege mit linearen Ungleichungen
Kapitel 3 Matchings in bipartiten Graphen
3.1 Definitionen
gerichteter Graph, Knoten, Kanten, Kantenfolge, Weg, Kreis, Nachbar, wegzusammenhängend, Zusammenhangskomponente, zusammenhängend, bipartit
5. Freitag, 25. April 2014 (pdf)
3.2 Matchings mit maximaler Kardinalität 
Def: M-augmentierender Weg
Satz: Entweder ist M Matching mit maximaler Kardinalität oder es gibt einen M-augmentierenden Weg
Algorithmus zur Bestimmung eines Matchings mit maximaler Kardinalität
Residualgraph zur Bestimmung eines M-augmentierenden Wegs in bipartiteten Graphen
3.3 Das Matching Theorem von König
Def: Knotenüberdeckung
Satz: Sei G bipartiter Graph, dann ist die maximale Kardinalität eines Matchings in G gleich der minimalen Kardinalität einer Knotenüberdeckung in G
6. Mittwoch, 30. April 2014 (pdf)
3.4 Matchings mit maximalem Gewicht
Def: extremes Matching
Def: Längenfunktion
Satz: Augementierung eines extremen Matchings mit Hilfe eines M-augmentierenden Weg minimaler Länge
Algorithmus: Die ungarische Methode
Satz: Residualgraph hat keine gerichteten Kreise negativer Länge
7. Freitag, 2. Mai 2014 (pdf)
Kapitel 4 Flüsse in Netzwerken
4.1 Das Max-Flow-Min-Cut Theorem
Def: s-t-Fluss
Lemma: Wert eines s-t-Flusses ist durch Kapazität eines s-t-Schnitts beschränkt
Def: Residualgraph
Lemma: Erkennung eines maximalen Flusses durch Residualgraph
Theorem: Max-Flow = Min-Cut
Korollar: ganzzahlige Kapazität => ganzzahliger maximaler Fluss
Algorithmus von Ford-Fulkerson
8. Mittwoch, 7. Mai 2014 (pdf)
Satz: Endlichkeit des Ford-Fulkerson-Algorithmus für rationale Kapazitäten
4.2 Verbesserung des Ford-Fulkerson-Algorithmus
Satz: (Dinits 1970, Edmonds-Karp 1972) Falls immer kürzeste s-t-Wege zur Flussverbesserung gewählt werden, ist die Anzahl der Iterationen höchstens |V| |A| (insbesondere unabhängig von den Kapazitäten)
9. Freitag, 9. Mai 2014 (pdf)
Teil II: THEORIE DER LINEAREN OPTIMIERUNG
Kapitel 5 Polyedertheorie
Lineares Programm
5.1 Konvexe Mengen
Def: Konvexkombination, Verbindungsstrecke, konvexe Menge
Satz: Charakterisierung von konvexen Mengen
10. Mittwoch, 14. Mai 2014 (pdf)
Bsp: Einheitskugel bzgl. einer Norm
Def: konvexe Hülle
Satz: Charakterisierung der konvexen Hülle
Def: Polytop
Def: affine Unabhängigkeit, Dimensions
Satz: Caratheodory
11. Freitag, 16. Mai 2014 (pdf)
5.2 Trenn- und Stützhyperebenen
Def: Hyperebene, Halbraum, Trennhyperebene, Stützhyperebene
Lemma: metrische Projektion
Theorem: Existenz von Trennhyperebenen
12. Mittwoch, 21. Mai 2014 (pdf)
Def: Polyeder
5.3 Extrempunkte und Ecken
Def: Extrempunkt, Ecke
Satz: Charakterisierung von Ecken eines Polyeders
Korollar: Polyeder besitzen nur endlich viele Ecken
13. Freitag, 23. Mai 2014 (pdf)
Theorem: (Minkowski) Beschränktes Polyeder ist Polytop
Def: Polare
Lemma: Eigenschaften der Polaren
Theorem: (Weyl) Polytop ist beschränktes Polyeder
14. Mittwoch, 28. Mai 2014 (pdf)
Def: konvexer Kegel
Def. und Satz: konische Hülle
Theorem: Polyeder sind genau die Minkowskisummen von Polytopen und konvexer Kegel
5.4 Lemma von Farkas
Satz: Lösbarkeitskriterium für lineare Gleichungssysteme
Satz: Farkas Lemma
Korollar: Variante von Farkas Lemma
15. Freitag, 30. Mai 2014 (pdf)
5.5 Lineare Programmierung
Def: Lineares Programm (LP)
Satz: Optimale Lösungen werden in Ecken angenommen
Def: Primales, duales LP
Satz: schwache Dualität
Satz: Optimalitätsbedingung, Komplementaritätsbedingung
16. Mittwoch, 4. Juni 2014 (pdf)
Theorem: Starke Dualität
Korollar: Variante des Dualitätstheorems
Kapitel 6 Ganzzahlige Optimierung und vollständig unimodulare Matrizen
6.1 Ganzzahlige lineare Programme
Def: Ganzzahliges LP in Standardform
Bsp: Matchingzahl eines Graphen als ganzzahliges LP
Dualitätsbeziehungen und P vs. NP-Problem (Millenium Prize)
Def: Ganzzahliges Polytop
17. Freitag, 6. Juni 2014 (pdf)
6.2 Vollständig unimodulare Matrizen
Def: Vollständig unimodulare (VU) Matrix
Satz: $A$ VU, $b$ ganzzahlig, dann ist jede Ecke von $P = \{x : Ax \leq b\}$ ganzzahlig
Def: Ganzzahliges Polyeder
Satz: $A$ VU, $b$ ganzzahlig, dann ist Polyeder $P = \{x : Ax \leq b\}$ ganzzahlig
Korollar: Ganzzahlige LP Dualität
Satz: (Hoffman-Kruskal) Charakterisierung von vollständig unimodularen Matrizen
18. Mittwoch, 18. Juni 2014 (pdf)
6.3 Vollständig unimodulare Matrizen und bipartite Graphen
Satz: Graph ist bipartit genau dann wenn seine Inzidenzmatrix vollständig unimodular ist
Korollar: Matchingtheorem von König
Korollar: Ungleichungsbeschreibung des Matchingpolytops von bipartiten Graphen
19. Freitag, 20. Juni 2014 (pdf)
Korollar: Theorem von Egervary über gewichtete Matchings in bipartiten Graphen
6.4 Vollständig unimodulare Matrizen und gerichtete Graphen
Satz: Inzidenzmatrizen von gerichteten Graphen sind vollständig unimodular
Korollar: Max-flow-min-cut Theorem
20. Mittwoch, 25. Juni 2014 (pdf)
TEIL III: ALGORITHMEN DER LINEAREN OPTIMIERUNG
Kapitel 7 Das Eliminationsverfahren von Fourier und Motzkin
7.1 Fourier-Motzkin Elimination
7.2 Das Lösen von linearen Programmen mit Fourier-Motzkin Elimination
7.3 Farkas Lemma mit Fourier-Motzkin
21. Freitag, 27. Juni 2014 (pdf)
Kapitel 8 Das Simplexverfahren
Algorithmus
22. Mittwoch, 2. Juli 2014 (pdf)
Satz: Simplexalgorithmus terminiert in endlich vielen Schritten
Finden einer Startecke
Zur praktischen und theoretischen Effizienz
23. Freitag, 4. Juli 2014 (pdf)
Kapitel 9 Die Ellipsoidmethode
24. Mittwoch 9. Juli 2014 
(pdf)
25. Freitag 11. Juli 2014 
(pdf)
Kapitel 10 Die Innere-Punkte-Methode
10.1 Der zentrale Pfad
26. Mittwoch 16. Juli 2014 (pdf)
10.2 Der Algorithmus uns seine Analyse
27. Freitag 18. Juli 2014 (pdf)