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.
- Von allen Teilnehmerinnen und Teilnehmern werden eine regelmäßige Teilnahme und eine aktive Mitarbeit erwartet.
- Die Vorträge sollen höchstens 75 Minuten dauern. Anschließend sind dann 15 Minuten für eine Diskussion vorgesehen.
- Alle Teilnehmerinnen und Teilnehmer müssen eine Zusammenfassung ihres Vortrags anfertigen, die mindestens eine und höchstens zwei Seiten lang ist.
- Alle Teilnehmerinnen und Teilnehmer müssen außerdem einen Probevortrag halten, der zwei bis drei Wochen vor dem eigentlichen Vortrag stattfindet. Ein erfolgreicher Probevortrag ist Voraussetzung für den Vortrag im Seminar.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner,
Dr. N. Hähnle