Institut für Theoretische Informatik, Algorithmik

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

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

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.