Kombinatorische Optimierung (Winter 2019/20)

Vorlesung: Donnerstags 15:00-16:30 im Curie-Hörsaal
Dozent: Jens M. Schmidt
Übung: Donnerstags 9:00 im Raum 112 (gerade Wochen)
Tutor: Jens M. Schmidt
SWS: 2V+1Ü
Zielgruppe: Mathematik Master 1. Fachsemester
Voraussetzungen: Einführung in OR und lineare Optimierung, Graphen und Algorithmen
Prüfung:


Prüfungsvoraussetzungen sind die regelmäßige und aktive Mitarbeit in den Übungen und das Vorstellen eigener Lösungen von Übungsaufgaben. Zum Ende der Vorlesungszeit wird eine mündliche Prüfung angeboten (eine Kombiprüfung ist möglich, diese bitte rechtzeitig anmelden).
Literatur:




  • B. Korte und J. Vygen - Combinatorial Optimization, 5th Edition, Springer, 2012.
  • W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver - Combinatorial Optimization, 1997.
  • A. Schrijver - Combinatorial Optimization - Polyhedra and Efficiency, Springer, 2003.
  • C. H. Papadimitriou, K. Steiglitz - Combinatorial Optimization, Dover, 1998.


Nr.
Inhalt Übung
01 MST Einführung und typische Probleme, Minimale Spannbäume, Generischer Algorithmus, Kruskal, Prim mit Laufzeiten
02 MST Boruvka, MSTs in O(m+n log log n), Linearzeit für Minoren-abgeschlossene Graphklassen, LP-Formulierung, (optional: Ganzzahligkeit des Spannbaumpolytops) ueb01.pdf


Reformationstag
03 Matroids Einführung in Matroide, Beispiele, Laminare Familien
04 Matroids Kreise und Eindeutigkeit, Greedy-Algorithmus, Rangfunktion, Modulare und Submodulare Funktionen und deren Eigenschaften, Lineare Hülle ueb02.pdf
05 Matroids Schnitt von Matroiden, Beispiele, Iteriertes Austauschlemma

06 Matroids Edmonds Matroid Intersection Algorithmus + Laufzeit, Schnitt dreier Matroide ueb03.pdf
07 Flows Definition Flüsse, Restnetzwerke, Max-Flow Min-Cut Theorem
08 Flows Ford Fulkerson, Rationale vs Irrationale Kapazitäten, Fat Pipe-Algorithmus ueb04.pdf
09 Flows Edmonds-Karp, Preflow-Push Algorithmen
10 Flows Preflow-Push mit Laufzeit O(n2 sqrt(m)) ueb05.pdf, Beispiel
11 Nowhere-Zero Flows Nowhere-Zero Flows, Tutte's Kardinalitätsargument, Äquivalenz zu Gruppenflüssen, Fluss-Färbungs-Dualität

12 Nowhere-Zero Flows Jaegers 4- und 8-Fluss-Theoreme, Reduktionen, Seymours 6-Fluss-Theorem
ueb06.pdf
13 Dynamic Programming Methoden für Optimierungsprobleme, Dynamische Programmierung: Fibonacci-Zahlen, Rucksack-Problem, Floyd-Warshall
14 Dynamic Programming Kürzeste Pfade, Dijkstra, Bellman-Ford ueb07.pdf
(15 Bonus)
Branch & Bound Branch & Bound, Branch & Cut, Metrisches TSP, MST-Approximation, Christofides ueb08.pdf (Bonus)