Proseminar: Algorithmen für NP-schwere Probleme
im Sommersemester 2021
Thema
Wir beschäftigen uns mit Approximationsalgorithmen für NP-schwere Probleme. Diese Algorithmen zeichnen sich dadurch aus, dass sie Lösungen berechnen, für deren Güte Garantieren bewiesen werden können. Wir decken dabei sowohl verschiedene Probleme als auch verschiedene Techniken des Algorithmendesigns ab.
Voraussetzungen
- Dieses Proseminar basiert auf und vertieft algorithmische Kenntnisse aus der Vorlesung „Theoretische Grundlagen der Informatik“.
- Die Kenntnis von Graphen, grundlegenden Algorithmentechniken und Komplexitätsklassen wird vorausgesetzt.
Quellen und Betreuung
- Jeder Teilnehmer erhält ein Auszug aus einem Buch zur eigenhändigen Bearbeitung.
- Das Proseminar basiert auf dem Buch Approximation Algorithms von Vijay V. Vazirani.
- Die Themen werden am ersten Termin, dem 12.04. bekanntgegeben und verteilt.
- Jeder Teilnehmer wird von einem Mitarbeiter betreut. Dieser Mitarbeiter steht für Fragen und Hinweise nach voriger Absprache zur Verfügung.
Allgemeines
- Ort: Online (Zoom). Der Beitrittslink ist für angemeldete Teilnehmer im ILIAS-Kurs zugänglich.
- Zeit: Montags von 12:00 Uhr bis 13:30 Uhr.
- Sprache: Die Proseminarsprache ist Deutsch.
Anmeldung
- 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. Außerdem erstellt jeder Teilnehmer eine Ausarbeitung im Umfang von 10 Seiten.
- 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 Ausarbeitungen sind spätestens zwei Wochen nach dem Vortrag für Feedback an den jeweiligen Betreuer abzugeben. Die finale Abgabe erfolgt eine Woche nach Erhalt des Feedbacks.
- Die Seminarnote ergibt aus der Note für den Vortrag und die Ausarbeitung, sowie der Beteiligung am Seminar.
Zeitplan
| # | Termin | Betreuung | Thema | Vortragende |
|---|---|---|---|---|
| 1 | 12.04. | – | Einführung und Themenvergabe | Thomas, Torsten, Matthias |
| 2 | 19.04. | – | „How to Vortrag“ und Ipe-Tutorial | Torsten, Matthias |
| 3 | 26.04. | – | Kurzvorträge | alle |
| 4 | 03.05. | – | Einführung in lineare Programme und Dualität | Thomas |
| 5 | 10.05. | Jonas | 1. Introduction + Set Cover | Robert |
| 10.05. | Lars | 2. Steiner Tree and TSP | Rafael | |
| 6 | 17.05. | Adrian | 3. Multiway Cut and k-Cut | Bill |
| 17.05. | Tim | 4. k-Center | Benedikt | |
| 7 | 31.05. | Laura | 5. Feedback Vertex Set | Fritz |
| 31.05. | Chris | 6. Shortest Superstring | Marius | |
| 8 | 07.06. | Marcus | 7. Euclidean TSP + Knapsack | Johannes |
| 07.06. | Paul | 8. Bin Packing + Minimum Makespan Scheduling | Jan | |
| 9 | 14.06. | Thomas | 9. Set Cover via Dual Fitting | Florian |
| 14.06. | Matthias | 10. Rounding Applied to Set Cover | Dominik | |
| 10 | 21.06. | Torsten | 11. Set Cover via the Primal-Dual Schema | Dennis |
| 21.06. | Sascha | 12. Maximum Satisfiability | Niko |
Änderungen vorbehalten.
Vorlagen
- Bitte verwenden Sie diese LaTeX-Vorlage für die Ausarbeitung.
- Präsentationsvorlagen für Ipe finden Sie auf der Seite des Ipe-Tutorials.
Materialien zu LP & Dualität
Ipe-Tutorial
- Informationen zu Ipe und die Arbeitsmaterialien des Ipe-Tutorials finden Sie auf der allgemeinen Seite des Ipe-Tutorials.
- Dort finden Sie ebenfalls Präsentationsvorlagen für Ipe.