Navigation

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:

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

Ort und Zeit der Übungen:

Donnerstag, 14:15 – 15:45 Uhr, Raum 01.150-128

Termine:

  • 21. April 2020: Beginn der Vorlesungen
  • 30. April 2020: Beginn der Übungen
  • Die Vorlesung entfällt am 2. Juni (Dienstag nach Pfingsten – Bergdienstag).
  • Die Übung entfällt am 21. Mai (Himmelfahrt) und am 11. Juni (Fronleichnam).

Video-Aufzeichung:

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

Wegen der Corona-Einschränken wird die Lehrveranstaltung bis auf Weiteres „digital“ bzw. „online“ stattfinden. Bitte melden Sie sich bei StudOn an und Sie werden weitere Informationen zu gegebener Zeit per Email von uns erhalten.

Anmeldung:

Bitte melden Sie sich im StudOn für den Kurs zur Vorlesung an. Diese Anmeldung dient nicht der Prüfungsanmeldung sondern führt lediglich dazu, dass Sie in den Mailverteiler zu dieser Vorlesung aufgenommen werden.

Übungsblätter:

 

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.