Vorlesung Kombinatorische Optimierung

Termine

• Mittwochs, 16:00-17:30, SR 055
• Donnerstags, 14:15-14:45, SR 055
• Übungen (Britta Broser): Montags, 10.15-11:45

Übungsblätter

1. Übungsblatt vom 18.4.
2. Übungsblatt vom 24.4.
3. Übungsblatt vom 2.5.
4. Übungsblatt vom 15.5.
5. Übungsblatt vom 12.6.
6. Übungsblatt vom 12.6.
7. Übungsblatt vom 19.6.
8. Übungsblatt vom 27.6.

Übersicht über die gehaltenen Vorlesungen

• Mittwoch, 17.4.2002
• Einleitung, Übersicht, kombinatorische Optimierungsprobleme
• Paarungen; der Satz von Berge über größte Paarungen
• Donnerstag, 18.4.2002
• Unabhängigkeitssysteme
• der gierige Algorithmus
• Matroide: Austauschaxiom, Basen, Kreise
• Gale-Ordnung, Gale-Optimalität
• Charakterisierung von Matroiden durch Gale-Optimalität und den gierigen Algorithmus
• Mittwoch, 24.4.2002
• Optimalität und Gale-Optimalität
• Charakterisierung von Matroiden (Fortsetzung)
• Rang
• submodulare Funktionen
• Beispiel: Standortproblem
• Donnerstag, 25.4.2002
• Beschreibung kombinatorischer Optimierungsprobleme durch Variablen und Ungleichungen
• Rangungleichungen für Matroide
• Abschluss in Matroiden
• Gradungleichungen für Paarungen
• Dualität für lineare Programme (Einführung)
• Donnerstag, 2.5.2002
• Lineare Programmierung
• Formulierung, Standardform
• geometrische Grundlagen: Hyperebenen und Halbräume, Konvexität, Polyeder
• duale lineare Programme
• schwacher und starker Dualitätssatz
• Mittwoch, 8.5.2002
• Das Lemma von Farkas
• Satz vom komplementären Schlupf
• Mittwoch, 15.5.2002
• Schlupfvariablen
• Ecken und Basislösungen
• Donnerstag, 16.5.2002
• der Simplexalgorithmus
• Mittwoch, 22.5.2002: entfällt
• Donnerstag, 23.5.2002: entfällt
• Mittwoch, 29.5.2002
• Kreisen im Simplexalgorithmus
• Donnerstag, 30.5.2002
• Dualität im Simplexalgorithmus; der duale Simplexalgorithmus
• Mittwoch, 5.6.2002: entfällt
• Donnerstag, 6.6.2002: entfällt
• Mittwoch, 12.6.2002
• der primal-duale Ansatz
• kürzeste Wege
• Donnerstag, 13.6.2002
• größter Fluss
• Mittwoch, 19.6.2002
• Ganzzahligkeit; Optimalitätskriterium
• Varianten des Flussproblems
• Flüsse mit kleinsten Kosten; Optimalitätskriterium
• Bestimmen von negativen Kreisen
• Donnerstag, 20.6.2002
• Kreise mit kleinsten durchschnittlichen Kosten
• Algorithmus von Goldberg und Tarjan für optimale Flüsse durch Vermehren über Kreise mit kleinsten durchschnittlichen Kosten
• Mittwoch, 26.6.2002
• größte Paarungen
• der Blütenalgorithmus von Edmonds
• Donnerstag, 27.6.2002
• ungerade Überdeckungen, max-min-Charakterisierung von größten Paarungen
• erwähnt: Satz von Tutte über größte Paarungen
• Das Paarungspolytop
• Mittwoch, 3.7.2002: entfällt
• Donnerstag, 4.7.2002: entfällt wegen Krankheit
• Mittwoch, 10.7.2002
• Paarungen mit kleinsten Kosten, primal-dualer Ansatz
• Charakterisierung des Paaaarungspolytops
• Donnerstag, 11.7.2002
• Paarungen mit kleinsten Kosten, Algorithmus
• Mittwoch, 17.7.2002
• Schnitt von zwei Matroiden
• Donnerstag, 18.7.2002
• stabile Heiraten