Seiteninterne Suche

Lehre

Approximationsalgorithmen

Dozent:

Prof. Dr. rer. nat. 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:

Montag, 12:15 – 13:45 Uhr, Raum 01.255-128

Ort und Zeit der Übungen:

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

Termine:

  • Die Vorlesung beginnt am 24. April.
  • Der Übungsbetrieb beginnt am 4. Mai.
  • Die Vorlesung und die Übung entfallen am 1. Mai (Tag der Arbeit), am 25. Mai (Christi Himmelfahrt), am 5. Juni (Pfingstmontag) und am 15. Juni (Fronleichnam).

Video-Aufzeichung:

Die Video-Aufzeichung vom Sommersemester 2014 ist hier aus dem Uni-Netz frei zugänglich.

Anmeldung:

Bitte melden Sie sich im EST für die Vorlesung an. Benutzen Sie im EST die Veranstaltungsanmeldung. Dort können Sie die Veranstaltung Approximationsalgorithmen (SS 17) auswählen. Das Anmeldepasswort erhalten Sie in der Vorlesung und in der Übung. Als Bestätigung für die erfolgreiche Anmeldung erhalten Sie eine Email. Diese Anmeldung dient nicht der Prüfungsanmeldung sondern führt lediglich dazu, dass Sie in den Mailverteiler zu dieser Vorlesung aufgenommen werden.

Übungsblätter:

Blatt 1 Blatt 2 Blatt 3
Blatt 4 Blatt 5 Blatt 6
Blatt 7 Blatt 8 Blatt 9

 

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.