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.
| 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.