direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

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.

News

    • Course materials such as slides etc. can be found here.
    • Possible dates for the oral exams are March 2 as well as April 4 (and April 5, if needed). More details will be announced towards the end of the semester.
    • Change of room: On Tuesday, Nov. 22, the lecture will be held in room MA751

    Contact Information

    The classes are given by Martin Skutella.

    Sporadic exercise sessions are given by Leon Sering.

    Office hours:  on demand

    Schedule

    Weekday
    Hour
    Room
    Lecture
    Monday
    10:15-11:45
    MA 313/314
    Lecture
    Tuesday
    10:15-11:45
    MA 313/314

    Literature

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

    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

    Zusatzinformationen / Extras

    Quick Access:

    Schnellnavigation zur Seite über Nummerneingabe

    This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.