VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

251-0423-00L 5 Credits

Approximation: Theorie und Algorithmen

Lecturers & Examiners: Prof. em. Dr. Peter Widmayer, Dr. Maurice Cochand, Prof. Dr. Bernd Gärtner, Prof. Dr. Thomas Erlebach, Prof. Dr. Angelika Steger
VVZ CR n/a

Last Updated: 2026-02-05 14:53:08

Objective

Verständnis für die Approximation schwerer kombinatorischer Optimierungsprobleme erwerben.

Content

Die Vorlesung beschäftigt sich mit Approximationsalgorithmen für NP-schwere Optimierungsprobleme. Da für solche Probleme vermutlich keine effizienten exakten Algorithmen existieren, interessiert man sich für beweisbar gute Näherungen, die in polynomieller Zeit berechenbar sind. Wir werden anhand einiger einfacher Approximationsalgorithmen die Thematik einführen, Standardtechniken wie LP-Relaxierung und Derandomisierung besprechen, aber auch neuere Methoden wie semidefinites Programmieren. Zum Abschluss der Vorlesung gehen wir auf Nichtapproximierbarkeitsresultate ein. Insbesondere werden wir probabilistisch überprüfbare Beweise (probabilistically checkable proofs (PCP)) und ihre Verbindung zu Nichtapproximierbarkeitsresultaten behandeln.

Resources

Literature

- V. Vazirani: Approximation Algorithms, Springer-Verlag, 2001

General Information

Language
German
Frequency
Yearly recurring

Examination

Type
session examination
Mode
oral 30 minutes

Course Components

Type Title Time & Place Hours
lecture Approximation: Theorie und Algorithmen
  • Thu 15:15-17:00 (IFW A 36)
2 h weekly
exercise Approximation: Theorie und Algorithmen
  • Thu 17:15-18:00 (IFW A 36)
1 h weekly

Offered In