Forschungsinstitut für Diskrete Mathematik

Hauptseminar Diskrete Optimierung

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:



Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner