English English

Veranstalter

Inhalt

Viele Optimierungsprobleme sind NP-schwer, d.h. für diese Probleme kann kein Algorithmus mit polynomieller Laufzeit gefunden werden, der für alle Instanzen eine optimale Lösung findet, wenn P ungleich NP ist. Eine Möglichkeit, dieses Problem anzugehen, ist, auf eine optimale Lösung zu verzichten und nur eine approximative Lösung zu berechnen. Die Theorie der Approximationsalgorithmen beschäftigt sich mit dieser Möglichkeit. Zum Beispiel können in einigen Fällen polynomielle Algorithmen angegeben werden, die eine Lösung berechnen, welche beliebig nahe bei einer optimalen Lösung liegt, während es für andere Probleme genauso schwer ist, eine approximative Lösung zu finden, wie das Problem optimal zu lösen. Das Seminar wird anhand ausgewählter Themen aus dem Bereich der Approximationsalgorithmen grundlegende Techniken und Konzepte dieses Gebietes der Algorithmik behandeln.

Als Teilnehmer werden Sie in Gruppenarbeit einem Vortrag von 90 Minuten Dauer (ca. 45 Minuten je Teilnehmer) zu einem Thema ausarbeiten. Der Inhalt sollte möglichst verständlich präsentiert werden. Der Vortrag sollte dabei nicht vornehmlich den Seminarleiter ansprechen sondern insbesondere Ihre Komilitonen. Der Inhalt der Vorlesung Approximationalgorithmen wird vorausgesetzt.

Termine

  • Mittwoch 5. April, 17:15 Uhr, Raum 4017: Themenvergabe
  • Dienstag 20. Juni, 17:00 Uhr, Raum 4017: Kurzpräsentation (maximal 4 Minuten pro Teilnehmer)
  • Freitag 18. August: Abgabe der Ausarbeitungen (maximal 4 Seiten pro Teilnehmer)
  • 18.-20. September: Vorträge (45 Minuten pro Teilnehmer, inklusive Diskussion)
Montag
Dienstag
Mittwoch
14:00 - 15:30
Facility Location Maximum Satisfiability Multicut in General Graphs
15:45 - 17:15
Steiner Forest Metric Approximation Sparsest Cut
17:30 - 19:00
Hardness of Approximation    

Vorlage für die Ausarbeitung

Themen

  • Metric Approximation: [FRT03]
    Daniel Plugge und Frank van der Beek, Betreuer: Matthias Englert
  • Maximum Satisfiability: Kapitel 16 aus [V01]
    Volker Wetzelaer und Hanno Wirtz, Betreuer: Matthias Westermann
  • Multicut in General Graphs: Kapitel 20 aus [V01]
    Stefan Heukamp und Stefan Mau, Betreuer: Matthias Englert
  • Sparsest Cut: Kapitel 21 aus [V01]
    Deniz Özmen und Martin Weck, Betreuer Matthias Westermann
  • Steiner Forest: Kapitel 22 aus [V01]
    Yan Gao und Wei Zhong, Betreuer: Matthias Englert
  • Facility Location: Kapitel 24 aus [V01]
    Christian Martelock und Alexandru Mereacre, Betreuer: Matthias Westermann
  • Hardness of Approximation: Kapitel 29 aus [V01]
    Ming Zhang und Yu Zhang, Betreuer: Matthias Westermann

Literatur