Kombinatorische Optimierung

Vorlesung: Donnerstag 13:00-14:30 im Curie-Hörsaal
Dozent: Jens M. Schmidt
Übung: Dienstag 17:00-18: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
15.10.2015 MST Einführung und typische Probleme, Minimale Spannbäume, Generischer Algorithmus, Kruskal, Prim mit Laufzeiten ueb01.pdf
22.10.2015 MST Boruvka, MSTs in O(m+n log log n), Linearzeit für Minoren-abgeschlossene Graphen
29.10.2015 Matroids LP-Formulierung, Satz vom komplementären Schlupf, Spannbaumpolytop und dessen Ganzzahligkeit, Einführung in Matroide, Laminare Familien ueb02.pdf
05.11.2015 Matroids Kreise und Eindeutigkeit, Greedy-Algorithmus, Rangfunktion und Submodularität, Lineare Hülle
12.11.2015 Matroids Schnitt von Matroiden, Edmond's Matroid Intersection Algorithmus + Laufzeit, Schnitt dreier Matroide
ueb03.pdf
19.11.2015 Flows Definition Flüsse, Restnetzwerke, Max-Flow Min-Cut Theorem
26.11.2015 Flows Ford Fulkerson, Rationale vs Irrationale Kapazitäten, Fat Pipe-Algorithmus ueb04.pdf
03.12.2015 Flows Edmonds-Karp, Preflow-Push Algorithmen
10.12.2015 Flows Preflow-Push mit Laufzeit O(n2 sqrt(m)) ueb05.pdf
17.12.2015 Flows & Matchings Erweiterungen: Flüsse mit Kanten- und Knotenbedarf, Folgerungen: Satz von Hall, Disjunkte Pfade und Menger-Theorem
07.01.2016 Nowhere-Zero Flows Nowhere-Zero Flows, Äquivalenz zu Gruppenflüssen, Fluss-Färbungs-Dualität, 5-Flow Conjecture
14.01.2016 Dynamic Programming Methoden für Optimierungsprobleme, Dynamische Programmierung: Fibonacci-Zahlen, Rucksack-Problem, Floyd-Warshall
ueb06.pdf
21.01.2016 Connectivity Algorithmen für Knoten- und Kantenzusammenhang, Maximum Adjacency Orderings, Min-Cut: Stoer-Wagner
28.01.2016 Connectivity Fluss-äquivalente Graphen, Gomory-Hu-Bäume
ueb07.pdf
04.02.2016 Branch & Bound Branch & Bound, Branch & Cut, Metrisches TSP, MST-Approximation, Christofides