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:

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