Wintersemester 2017/18
Thema: Exakte Algorithmen für NP-schwere Probleme
Wenn man Optimallösungen NP-schwerer Probleme berechnen will, muss man (unter der Annahme, dass P nicht gleich NP ist), nicht-polynomielle Laufzeiten akzeptieren. Doch zwischen solchen nicht-polynomiellen Laufzeiten gibt es starke Unterschiede, unter Umständen lassen sich auch noch recht große Instanzen mit ihnen lösen. In diesem Seminar werden wir möglichst effiziente exakte Verfahren zur Lösung NP-schwerer Probleme untersuchen. Die Hauptquelle für die Vorträge wird das unten angegebene Buch sein.| Nr. | Probevortrag 16 Uhr c.t. |
Vortrag 14 Uhr c.t. |
Name | Thema | Betreuung |
|---|---|---|---|---|---|
| 1 | 9.10. (14 Uhr) | 23.10. | Paul Timme | Kernelization I (Kapitel 2.1 - 2.3.1) | Vera Traub |
| 2 | 16.10. | 6.11. | Alexander Zorn | Kernelization II (Kapitel 2.3.2 - 2.6) | Pascal Cremer |
| 3 | 23.10. | 13.11. | Martin Spittel | Bounded search trees (Kapitel 3.1 - 3.4) | Siad Daboul |
| 4 | 6.11. | 20.11. | Janina Vogl | Iterative compression (Kapitel 4.1 - 4.3.1) | Niko Klewinghaus |
| 5 | 13.11. | 27.11. | Meike Neuwohner | Randomized methods (Kapitel 5.1 - 5.3 und 5.5) | Philipp Ochsendorf |
| 6 | 20.11. | 4.12. | Anna Köhne | Dynamic programming; ILPs; graph minors and the Robertson-Seymour Theorem (Kapitel 6) | Anna Hermann |
| 7 | 27.11. | 11.12. | Jannis Blauth | Treewidth I (Kapitel 7.1 - 7.3.2) | Rudi Scheifele |
| 8 | 4.12. | 18.12. | Tobias Paszkiet | Treewidth II (Kapitel 7.3.3, 7.6 und 7.7) | Markus Ahrens |
| 9 | 11.12. | 8.1.2018 | Anna Heuser | Algebraic techniques (Kapitel 10.1 - 10.3) | Tilmann Bihler |
| 10 | 18.12. | 15.1. | Jan Hitzschke | Fixed-parameter intractibility (Kapitel 13.1 - 13.3) | Pietro Saccardi |
Literatur:
- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk und Saket Saurabh: Parameterized Algorithms, Springer, 2016
- 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