Approximationsalgorithmen

Dozent:

Prof. Dr. Rolf Wanka

Modulbeschreibung:

Approximationsalgorithmen

Umfang/Stunden:

V2 + Ü2, 7.5 ECTS

Zielgruppe:

Studenten der Informatik und CE,
Interessenten anderer Fächer, insbesondere Mathematik

Ort und Zeit der Vorlesung:

Donnerstag, 10:15 – 11:45 Uhr, Raum 00.151-113 Seminarraum

Ort und Zeit der Übungen:

Dienstag, 10:15 – 11:45 Uhr, Raum 01.150-128 Seminarraum

Termine:

  • 18. April 2024: Beginn der Vorlesungen
  • 23. April 2024: Beginn der Übungen

Video-Aufzeichung:

Die Video-Aufzeichung vom Sommersemester 2014 ist hier aus dem Uni-Netz frei zugänglich.
Bitte melden Sie sich im für den Kurs zur Vorlesung an. Link zur StudOn Anmeldung.
Die kursbegleitenden Materialien werden in StudOn zur Verfügung gestellt.

Beschreibung:

Für viele kombinatorische Optimierungsprobleme hat sich herausgestellt, daß sie vermutlich nicht durch schnelle exakte Algorithmen gelöst werden können, weshalb man sich mit Näherungslösungen zufrieden geben muß. In dieser Vorlesung werden Approximationsalgorithmen vorgestellt, die für eine Reihe populärer Optimierungsprobleme beweisbar gute Lösungen in vertretbarer Zeit berechnen.

Im ersten Teil der Veranstaltung werden die grundlegenden Begriffe vorgestellt, mit Beispielalgorithmen ausgeführt und jeweils die Grenzen aufgezeigt.

Im zweiten Teil werden allgemeine Techniken eingeführt und anhand instruktiver Beispiele mit Leben erfüllt.

Literatur:

  • R. Wanka. Approximationsalgorithmen – Eine Einführung Teubner, 2006.
    doi:10.1007/978-3-8351-9067-2
  • K. Jansen, M. Margraf. Approximative Algorithmen und Nichtapproximierbarkeit. de Gruyter, 2008
  • D. P. Williamson, D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.
  • D.-Z. Du, K.-I Ko, X. Hu. Design and Analysis of Approximation Algorithms. Springer, 2012.
    doi:10.1007/978-1-4614-1701-9
  • G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Complexity and Approximation – Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999.
  • E. W. Mayr, H. J. Prömel, and A. Steger (Hrsg.). Lectures on Proof Verification and Approximation Algorithms. Springer, 1998.
  • V. V. Vazirani. Approximation Algorithms. Springer, 2001.

Inhalte:

  • Grundlagen
    • Schnelle Algorithmen und hartnäckige Probleme
    • Approximation mit absoluter Güte
    • Approximation mit relativer Güte
    • Approximationsschemata
  • Techniken
    • Randomisierte Approximationsalgorithmen
    • Lineare Optimierung und Approximationsalgorithmen
    • Approximate Counting und die Monte-Carlo-Methode

Twenty Proofs of Euler’s Formula, gesammelt von David Eppstein.