Section outline

  • General

    Collapse all Expand all

  • Vorlesung Approximationsalgorithmen

    Scope: 5 ECTS, 2+2 SWS
    Time and Place: Lecture: Friday, 10:15–11:45, M2, ÜR I (first lecture on Oct. 18)
    Tutorial: Tuesday, 10:15–11:45 Uhr, M2, SE I (first tutorial on Oct. 22)
    Oral exam:   February 2024
    Target Group: Master Computer Science, Master Mathematics, Master Computational Mathematics
    Lecture: Prof. Alexander Wolff
    Tutorium: Klaus Biehler

  • 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).

    Bei Interesse der Teilnehmer*innen kann auch auf fortgeschrittene Techniken in diesem Themengebiet sowie die Grenzen von Approximierbarkeit eingegangen werden, welche anspruchsvollere mathematische Werkzeuge erfordern.

    Lernziele

    Am Ende dieses Kurses sollen die Teilnehmer*innen 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.

    Literatur zur Vorlesung

    Approximation Algorithms
    Vijay V. Vazirani
    Springer, 2003

    The Design of Approximation Algorithms
    David P. Williamson, David B. Shmoys
    Cambridge University Press, 2011
    Kostenlose Online-Version

  • Vorlesungsfolien

    • In the table below clicking on the date yields the printer version of the slides, clicking on the topic of a lecture yields the long version of the slides.
    • The videos were made by Joachim Spoerhase during covid years. Enjoy!
    Date Topic Videos (old!) Literature
    18.10.2024 Introduction and Vertex Cover Lecture 01 [Vazirani, Chapter 1]
    25.10.2024 Set Cover and Shortest Superstring Lecture 02 [Vazirani, Chapter 2]
    08.11.2024 Steiner Tree, approximation-preserving reduction, Multiway Cut Lecture 03 [Vazirani, Chapters 3+4]
    15.11.2024 Linear programming and LP-duality Lecture 04 [Vazirani, Chapter 12]

  • Übungsblätter (Exercise Sheets)