Forschungsinstitut für Diskrete Mathematik

Hauptseminar Diskrete Optimierung

Wintersemester 2014/15


Thema: Iterative Methoden in der Kombinatorischen Optimierung


Viele wichtige Probleme der kombinatorischen Optimierung können als ganzzahliges lineares Programm formuliert werden. Lässt man dann die Nebenbedingung der Ganzzahligkeit weg, erhält man eine Relaxierung des Problems, die sich effizient lösen lässt. In diesem Seminar werden Techniken vorgestellt, mit denen man, ausgehend von einer Lösung des relaxierten Problems, eine ganzzahlige Lösung erhält, indem man nach und nach Variablen auf ganzzahlige Werte rundet und fixiert. Es wird untersucht, wie sich diese iterative Technik auf unterschiedliche Optimierungsprobleme anwenden lässt.


Literatur: L.C. Lau, R. Ravi, M. Singh: Iterative Methods in Combinatorial Optimization. Cambridge University Press. 2011.


Vorträge:

Nr. Probevortrag
16 Uhr c.t.
Vortrag
14 Uhr c.t.
Name Thema Betreuung
1 6.10. 20.10. Lukas Naumann Assignments in bipartite graphs (3.2 - 3.3) Philipp Ochsendorf
2 13.10. 27.10. Fabian Zaiser Spanning trees (4.1, 4.3 und 4.4) Philipp Ochsendorf
3 20.10. 3.11. Daniel Wochnik Max-weight independent set, matroid intersection, and duality (5.2 - 5.4) Ulrike Schorr
4 27.10. 10.11. Andrei Sterin Bounded degrees and k matroid intersection (5.5 und 5.6) Ulrike Schorr
5 3.11. 17.11. Florian Bohl Arborescences (6.1 und 6.2) Daniel Rotter
6 10.11. 24.11. Friederike Michaelis Submodular flows (7.1 - 7.4) Rudi Scheifele
7 17.11. 1.12. Vera Traub Network matrices (8.1 - 8.4) Anna Hermann
8 24.11. 8.12. Tilman Bihler Matchings (9.1) Jannik Silvanus
9 1.12. 15.12. Paul Stahr Network design (10.1 - 10.3) Rudi Scheifele
10 8.12. 22.12. Britta Heymann Constrained optimization problems (11.1 - 11.3) Niko Klewinghaus
11 15.12. 12.1.2015 Khai Van Tran Cut problems (12.1 - 12.3) Markus Ahrens
12 22.12. 19.1. Xianghui Zhong Rearrangement of sums and unsplittable flows (13.1, 13.2 und 13.4) Niko Klewinghaus
13 12.1. 26.1. Maike Grewing Steiner trees (13.6) Daniel Rotter

Die ersten beiden Kapitel sollte jeder vor Beginn des Seminars gelesen haben. Die Nummern bei den einzelnen Vorträgen beziehen sich auf die Teile eines Kapitels, die schwerpunktmäßig vorgetragen werden sollen. Jeder sollte aber sein gesamtes Kapitel gelesen haben und auch die übrigen Kapitelabschnitte bei seinem Vortrag berücksichtigen.



Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner,
Dr. N. Hähnle