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 (ungerade 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. Am Ende des Semesters 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
13.10.2016 MST Einführung und typische Probleme, Minimale Spannbäume, Generischer Algorithmus, Kruskal, Prim mit Laufzeiten ueb01.pdf
20.10.2016 MST Boruvka, MSTs in O(m+n log log n), Linearzeit für Minoren-abgeschlossene Graphklassen, LP-Formulierung
27.10.2016 Matroids Ganzzahligkeit des Spannbaumpolytops, Einführung in Matroide, Beispiele ueb02.pdf
03.11.2016 Matroids Laminare Familien, Kreise und Eindeutigkeit, Greedy-Algorithmus, Rangfunktion, Modulare und Submodulare Funktionen und deren Eigenschaften, Lineare Hülle
10.11.2016 Matroids Schnitt von Matroiden, Beispiele, iteriertes Austauschlemma
ueb03.pdf
17.11.2016 Matroids Edmonds Matroid Intersection Algorithmus + Laufzeit, Schnitt dreier Matroide
24.11.2016 Flows Definition Flüsse, Restnetzwerke, Max-Flow Min-Cut Theorem ueb04.pdf
01.12.2016 Flows Ford Fulkerson, Rationale vs Irrationale Kapazitäten, Fat Pipe-Algorithmus
08.12.2016 Flows Edmonds-Karp, Preflow-Push Algorithmen ueb05.pdf
15.12.2016 Flows Preflow-Push mit Laufzeit O(n2 sqrt(m))
22.12.2016 Nowhere-Zero Flows Nowhere-Zero Flows, Tutte's Kardinalitätsargument, Äquivalenz zu Gruppenflüssen, Fluss-Färbungs-Dualität
ueb06.pdf
12.01.2017 Nowhere-Zero Flows Jaegers 4- und 8-Fluss-Theoreme, Reduktionen, Seymours 6-Fluss-Theorem

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