Themen dieses Kurses

  • Vorlesung Approximationsalgorithmen

    Umfang:

    5 ECTS, 2+2 SWS [T:2,P:0]

    Zeit & Ort:

    Vorlesung freitags, 10:15-11:45 Uhr, ÜR I
    Übung dienstags, 10:15-11:45 Uhr, SE I

    Mdl. Prüfungen:  

    tba

    Zielgruppe:

    Master Informatik, Master Mathematik, Master Computational Mathematics

    Dozenten:

    Thomas van Dijk und Alexander Wolff

    Übung:

    Myroslav Kryven


    Schreiben Sie sich für die Teilnahme an der Vorlesung bitte in den WueCampus-Kurs ein!

    • Kursbeschreibung

      Inhalt

      Die Aufgabe eine optimale Lösung für ein gegebenes Problem (Optimierungsproblem) zu ermitteln ist allgegenwärtig in der Informatik. Ein prominentes Beispiel ist das Problem des Handlungsreisenden, bei dem es darum geht eine kürzeste Rundreise zu finden, die eine vorgegebene Menge von Stationen besucht. Leider ist für eine Vielzahl solcher Probleme kein effizienter Algorithmus bekannt, der eine optimale Lösung ermittelt. In der Praxis verwendet man daher häufig Verfahren, die zwar nicht immer optimale aber dafür stets gute Lösungen liefern.

      In dieser Vorlesung beschäftigen wir uns mit Entwurfs- und Analysetechniken für solche Algorithmen. Wir betrachten Verfahren, die eine nachweisbare Approximationsgüte besitzen. Unter Approximationsgüte versteht man das Verhältnis zwischen der Qualität einer approximativen Lösung und einer optimalen Lösung. Zum Beispiel garantiert ein Algorithmus mit Approximationsgüte 2 für das Problem des Handlungsreisenden für jede Eingabe eine Rundreise zu finden, die höchstens doppelt so lang ist wie die kürzeste Rundreise (die im Allgemeinen nachweislich schwer zu berechnen ist).

      Lernziele

      Am Ende dieses Kurses sollen die Teilnehmer in der Lage sein, einfache Approximationsverfahren bezüglich ihrer Güte zu analysieren. Außerdem sollen sie grundlegende Entwurfstechniken, wie beispielsweise Greedy, lokale Suche, Skalierung, und LP-basierte Methoden, verstehen und anwenden können.


      Bücher zur Vorlesung

      • Approximation Algorithms
        Vijay V. Vazirani
        Springer, 2003
      • The Design of Approximation Algorithms
        David P. Williamson und David B. Shmoys
        Cambridge University Press, 2011
        Kostenlose Online-Version
      • Approximationsalgorithmen: eine Einführung
        Rolf Wanka
        Teubner Wiesbaden, 2006
        Onlineversion erhältlich im Uni-Netz
      • Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties
        Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela und Marco Protasi
        Springer, 1999
      • Approximative Algorithmen und Nichtapproximierbarkeit
        Klaus Jansen und Marian Margraf
        de Gruyter Berlin, 2008
      • Vorlesungsfolien

        • Übungsblätter