Sie sind hier

Proseminar "Approximationsalgorithmen"

Überblick

Viele praktisch relevante Optimierungsprobleme sind kategorisch schwierig und können nicht durch einen effizienten Algorithmus gelöst werden. In vielen Bereichen ist es allerdings nicht immer notwendig, dass eine optimale Lösung berechnet werden muss. Oft genügt es eine "einigermaßen gute" Lösung zu berechnen. Approximationsalgorithmen sind Algorithmen, die eine gewisse Güte bei der Lösung in akzeptabler Zeit garantieren, dafür aber nicht notwendigerweise eine optimale Lösung berechnen. In diesem Proseminar wird das Gebiet der Approximationsalgorithmen problemorientiert angegangen, sowie verschiedene Techniken diskutiert und analysiert.

Veranstalter: Matthias Thimm

Seminarthemen

Jedes Seminarthema hat ein bestimmtes Problem im Fokus. Die Hauptquelle für alle Seminarthemen ist [2].

  1. Das Mengenüberdeckungsproblem [2, Kapitel 2]
  2. Das Steinerbaumproblem und das Problem des Handlungsreisenden [2, Kapitel 3]
  3. Schnittprobleme [2, Kapitel 4]
  4. Das metrische Facility Location Problem [2, Kapitel 5]
  5. Das Problem der kreiskritischen Knotenmenge [2, Kapitel 6]
  6. Das Shortest Superstring Problem [2, Kapitel 7]
  7. Das Rucksackproblem [2, Kapitel 8]
  8. Das Behälterproblem [2, Kapitel 9]
  9. Das Job Scheduling Problem [2, Kapitel 10]
  10. Das Euklidische Problem des Handlungsreisenden [2, Kapitel 11]

Jedes Thema kann von 1-2 Studierenden bearbeitet werden. Wird ein Thema von zwei Studierenden bearbeitet, so sind ggfs. weiterführende Techniken aus Kapiteln 12-30 dem Thema hinzuzufügen. Die Quellen [1, 3] können alternativ und weiterführend genutzt werden.

Literaturempfehlungen

  1. Juraj Hromkovic. Algorithmics for hard problems. Springer, 2001.
  2. Vijay V. Vazirani. Approximation algorithms. Springer, 2001.
  3. Rolf Wanka. Approximationsalgorithmen - Eine Einf ̈uhrung. Teubner, 2006.

Termine

Vorbesprechung: 15.02.2018 14:15 (Raum B.013)

Proseminar: Montags 14:15-15:45 Uhr (Raum TBA)

Teilnahme

Um an dem Proseminar teilzunehmen ist eine Teilnahme an der Vorbesprechung am 15.02.2017 14:15 (Raum B.013) erforderlich. Wenn Sie Interesse haben an dem Proseminar teilzunehmen, kündigen Sie dies bitte vorab in einer informellen E-Mail an Matthias Thimm an.

Von den Teilnehmern wird eine Präsentation (ca. 30 Minuten) über eines der oben genannten Themen erwartet. Im Anschluss an das Proseminar ist eine Ausarbeitung über das Seminarthema (ca. 12 Seiten) abzugeben.

Bitte beachten Sie bei der Erstellung der Präsentation und der Ausarbeitung folgende allgemeine Richtlinien (nur in Englisch verfügbar): pdf

Veranstaltung in KLIPS: Proseminar