Kombinatorische Optimierung

Vorlesung: Donnerstag 13:00-14:30 im Curie-Hörsaal
Dozent: Jens M. Schmidt
Übung: Mittwoch 09:00-10:30 im Raum C112 (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.


Datum Inhalt Übung
12.10.2017 MST Einführung und typische Probleme, Minimale Spannbäume, Generischer Algorithmus, Kruskal, Prim mit Laufzeiten ueb01.pdf
19.10.2017 MST Boruvka, MSTs in O(m+n log log n), Linearzeit für Minoren-abgeschlossene Graphklassen, LP-Formulierung
26.10.2017 Matroids Ganzzahligkeit des Spannbaumpolytops, Einführung in Matroide, Beispiele, Laminare Familien ueb02.pdf
02.11.2017 Matroids Kreise und Eindeutigkeit, Greedy-Algorithmus, Rangfunktion, Modulare und Submodulare Funktionen und deren Eigenschaften, Lineare Hülle
09.11.2017 Matroids Schnitt von Matroiden, Beispiele, Iteriertes Austauschlemma
ueb03.pdf
16.11.2017 Matroids Edmonds Matroid Intersection Algorithmus + Laufzeit, Schnitt dreier Matroide
23.11.2017 Flows Definition Flüsse, Restnetzwerke, Max-Flow Min-Cut Theorem ueb04.pdf
30.11.2017 Flows Ford Fulkerson, Rationale vs Irrationale Kapazitäten, Fat Pipe-Algorithmus
07.12.2017 Flows Edmonds-Karp, Preflow-Push Algorithmen ueb05.pdf
14.12.2017 Flows Preflow-Push mit Laufzeit O(n2 sqrt(m)) Beispiel
21.12.2017 Nowhere-Zero Flows Nowhere-Zero Flows, Tutte's Kardinalitätsargument, Äquivalenz zu Gruppenflüssen, Fluss-Färbungs-Dualität
ueb06.pdf
11.01.2018 Nowhere-Zero Flows Jaegers 4- und 8-Fluss-Theoreme, Reduktionen, Seymours 6-Fluss-Theorem

18.01.2018 Dynamic Programming Methoden für Optimierungsprobleme, Dynamische Programmierung: Fibonacci-Zahlen, Rucksack-Problem, Floyd-Warshall ueb07.pdf
25.01.2018 Dynamic Programming Kürzeste Pfade, Dijkstra, Bellman-Ford
01.02.2018 Branch & Bound Branch & Bound, Branch & Cut, Metrisches TSP, MST-Approximation, Christofides ueb08.pdf (Bonus)