Kombinatorische Optimierung
Sommersemester 2007
Prof. Dr. Friedrich Eisenbrand
| Vorlesung | Dienstag 14-16 (D2) Freitag 14-16 (D1) |
| Übung | Mittwoch 14-16 (N3.229) |
Inhalt
Die kombinatorische Optimierung ist ein recht junges Forschungsgebiet auf der Schnittstelle von Mathematik und Informatik. Anwendungen für kombinatorische Optimierungsprobleme sind im modernen Alltag überall zu finden insbesondere in Prodoktion, Planung und Logistik.
In dieser Vorlesung beleuchten wir diskrete Optimierungsprobleme, die sehr häufig Teilprobleme praktischer Optimierungsprobleme bilden. Hauptzugang zu behandelten effizienten Algorithmen ist hierbei die polyedrische Methode. Wir betrachten sowohl Probleme, die effizient lösbar sind, als auch Approximationsalgorithmen für NP-schwere diskrete Optimierungsprobleme.
Die Vorlesung baut auf Kenntnisse aus der linearen Optimierung auf, wie sie in Optimierung 1 erworben werden.
Aus dem Inhalt:
- Minimale Spannbäume
- Branchings und Arboresence
- Minimale Schnitte und Gomory-Hu Bäume
- Matchings und T-Joins
- Stabile Mengen und perfekte Graphen
- Mehrgüterflüsse und kantendisjunkte Wege
- Approximationsalgorithmen für Netzwerk Design, Bin Packing, Scheduling und Max-Cut
Zielgruppe
Vie Vorlesung richtet sich an Mathematiker und Informatiker. Für Mathematiker ist die Vorlesung eine weiterführende
Vorlesung im Bereich der angewandten Mathematik. Es kann ein Übungsschein erworben werden.
Für
Informatiker ist die Vorlesung eine Veranstaltung im Modul III.2.6 (3LP).
Kriterien zur Scheinvergabe
Am Ende der Veranstaltung wird es eine Prüfung geben. Ob diese mündlich oder schriftlich ist, hängt von der Teilnehmerzahl ab. Voraussetzung zur Zulassung zur Prüfung sind das Erreichen von mindesten 50% der möglichen Übungspunkte.
Literatur
- Alexander Schrijver, Combinatorial Optimization: Polhedra and Efficiency, Springer-Verlag
- Alexander Schrijver, A Course in Combinatorial Optimization
- Alexander Schrjver, Theory of Linear and Integer Programming, Wiley
- W. Cook, W.H. Cunningham, W.R. Pulleyblank and A. Schrijver, Combinatorial Optimization, Wiley-Interscience
- Eugene Lawler, Combinatorial Optimization, Networks and Matroids, Dover
- Vijay V. Vazirani, Approximation Algorithms, Springer-Verlag
- Bernhard Korte and Jens Vygen, Combinatorial Optimization: Theory and Algorithms, Springer-Verlag
Was wurde wann gemacht
Warnung: Die hier zur Verfügung gestellten Mitschriften dienen vor allem meiner eigenen Vorbereitung auf den Kurs. Sie sollten keinesfalls als alleinige Quelle zu den jeweiligen Themen für Ihre Nachbereitung verwendet werden. Lesen Sie unbedingt in der angegebenen Literatur. Die Bücher stehen in meinem Seminarapparat in der Bibliothek.
- 02.04: Wiederholung Lineares Programm, Dualitätstheorie, Faces, Darstellungssatz von Polyedern (Siehe Vorlesungsmitschrift aus dem letzten Semester)
- 10.04: Lösbarkeit von linearen GLS in den ganzen Zahlen, Hermite Normalform und Zertifikate (Mitschrift)
- 13.04: Gitter, Eindeutigkeit der HNF, TDI-Systeme, Bäume (Mitschrift)
- 17.04: Minimale Spannbäume, Waldpolytop, TDI-heit der Systeme ([1], Seiten 854-862)
- 20.04: Minimum weight Arborescences (Mitschrift)
- 24.04: Minimum weight arborescences: algorithm, min-max relation (Mitschrift)
- 27.04: Matroids: Greedy algorithm (Mitschrift)
- 04.05: Das duale Matroid und das Matroidpolytop ([1], Seiten 653-653, 690-692)
- 08.05: Matroid intersection (Mitschrift)
- 11.05: Weiter mit Matroid Intersection; Beginn Min Cuts und Random Contraction ([4] Kapitel 3.5, Lecture Notes von Luca Trevisan)
- 15.05: Deterministischer MinCut Algorithmus, Beginn Gomory-Hu Trees ([1], Seiten 244-246 und 248-258)
- 22.05: Weiter mit Gomory-Hu Trees, minimale ungerade Schnitte und max. weight. perfektes Matching (Separation der minimalen ungeraden Schnitte mit G-H Trees) ([1], Seiten 448-449)
- 25.05: Schranken an den Durchmesser von Polyedern (Barnette und Kalai & Kleitman)
- 29.05: Dear Algorithmus von Clarkson und abstrakte Optimierungsprobleme (Mitschrift, Folien)
- 01.06: Weiter mit Clarkson
- 05.06: APTAS for Bin Packing. (Lecture notes of Rajeev Motwain)
- 08.06: Weiter mit Bin Packing
- 12.06: Gitterbasisreduktion (Mitschrift)
- 15.06: Weiter mit Gitterbasisreduktion, LLL-Algorithmus
- 19.06: Ende LLL-Algrithmus, Ganzzahlige Programmierung in fester Dimension
- 23.06: Satz von Dirichlet und iteratives Runden (Mitschrift)
- 26.06: Satz von Frank und Tardos
- 29.06: Semidefinite Programming ([6], Chapter 26)
- 06.07: Max Cut Algorithmus und Beginn Perfekte Graphen
- 10.07: Weak Perfect Graph Theorem
- 13.07: Clique Polytop und Lovasz Theta Function