direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Approximation Algorithms (ADM III)

An approximation algorithm for an NP-hard optimization problem is a polynomial time algorithm that always finds a feasible solution whose value is provably close to the optimum solution value. More precisely, the value of the computed solution must be within a factor alpha of the optimum. alpha is the performance guarantee of the approximation algorithm.

The field of approximation algorithms is among the most active research areas of algorithmic discrete mathematics today. It combines a rich and deep mathematical theory with the promise of profound practical impact.

 In order to follow the course, profound knowledge of linear and combinatorial optimization is required.


    • Course materials such as slides etc. can be found here [1].
    • If you are interested in attending next semester's seminar on approximation algorithms, please send me an email.

    Contact Information

    The classes are given by Martin Skutella [2].

    Office hours:  on demand


    MA 749
    MA 751


    1. 29/10/2014: Solve Exercises 1.3, 1.5, 2.1, and 2.3 from the Williamson-Shmoys book. The solutions will be discussed in class on November 5.
    2. 07/11/2014: Solve Exercises 2.5, 2.16, 3.3, and 3.6 from the Williamson-Shmoys book. The solutions will be discussed in class on November 19.
    3. 05/12/2014: Solve Exercises 4.1, 4.3, 4.6, and 4.7 from the Williamson-Shmoys book. The solutions will be discussed in class on December 12.



    The course is based on selected chapters of the following book:

    • David P. Williamson, David B. Shmoys, The Design of Approximation Algorithms [3], Cambridge University Press, 2011

    Further reading:

    • G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer Verlag, 1999
    • D. S. Hochbaum (ed.), Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1995
    • B. Korte, J. Vygen, Combinatorial Optimization, Springer Verlag, 5th edition, 2012
    • V. V. Vazirani, Approximation Algorithms, Springer Verlag, 2001
    • M. R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979
    ------ Links: ------

    Zusatzinformationen / Extras


    Schnellnavigation zur Seite über Nummerneingabe

    Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.
    Copyright TU Berlin 2008