Proseminar: Algorithmen für NP-schwere Probleme
im Sommersemester 2018
Thema
- Wir beschäftigen uns exemplarisch mit einigen Algorithmen für NP-schwere Probleme. Diese Algorithmen zeichnen sich durch beweisbare Garantien aus. Dabei decken wir verschiedene Techniken des Algorithmendesigns ab.
Aktuelles
Allgemeines
- Organisation: Dr. Sascha Gritzbach, Prof. Dr. Dorothea Wagner
- Zeit: Montags von 11:30 Uhr bis 13:00 Uhr.
- Sprache: Die Proseminarsprache ist Deutsch.
Anmeldung
- Die Anmeldung für das Proseminar erfolgt per E-Mail bei Dr. Sascha Gritzbach.
- Die Teilnehmerzahl ist auf 12 beschränkt, die Plätze werden nach Anmeldereihenfolge vergeben.
- Alle Plätze sind belegt.
Ablauf
- Jeder Seminarteilnehmer hält einen fünfminütigen Kurzvortrag und einen 35-minütigen Vortrag im Proseminar und steht danach für Fragen der Teilnehmer zur Verfügung.
- Eine regelmäßige Teilnahme am Seminar wird vorausgesetzt.
- Spätestens zwei Wochen vor dem Vortragstermin ist das Vortragskonzept mit dem jeweiligen Betreuer zu besprechen.
- Ein vorläufiger Foliensatz ist eine Woche vor dem Vortrag beim jeweiligen Betreuer abzugeben.
- Die Seminarnote ergibt aus der Note für den Vortrag und Kurzvortrag, sowie der Beteiligung am Seminar.
Zeitplan
| # | Termin | Betreuung | Thema | Vortragende |
|---|---|---|---|---|
| 1 | 16.04. | Sascha | Einführung und IPE-Tutorial Folien | - |
| 2 | 23.04. | - | Kurzvorträge | alle |
| 3 | 07.05. | Michael | Exaktes Cluster Editing Folien | Hamid Doust |
| 4 | 07.05. | Valentin | Center Selection Problem Folien | Adrian Cierpka |
| 5 | 14.05. | Tim | Steiner-Baum-Problem Folien | Benedikt Wagner |
| 6 | 14.05. | Torsten | Vertex Ordering Problems Folien | Markus Schneckenburger |
| 7 | 28.05. | Sascha | Travelling Salesman Problem with Distances One and Two Folien | Sina Schmitt |
| 8 | 28.05. | Tobias | Approximation Schemes for the Restricted Shortest Path Problem Folien | Mazen Ebada |
| 9 | 25.06. | Guido | Label Placement by Maximum Independent Set in Rectangles Folien | Moritz Halm |
| 10 | 25.06. | Matthias | Independent Sets in Disk-Graphen | Sarah Engel |
| 11 | 02.07. | Marcel | Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth | Maximilian Felix Göckel |
| 12 | 02.07. | Lars | FPT-Algorithmus für Maximum-Weight Independent Set mittels Baumzerlegung Folien | Marc Jenne |
| 13 | 09.07. | Franziska | An Exact Exponential-Time Algorithm for Power Dominating Set | Marcus Schilling |
| 14 | 09.07. | Lukas | Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs | Fabian Frank |