The online sessions will now take place on Mondays at 12:00 noon, starting from November 16. Given the short notice, there is no zoom session on November 9.

Course material and videos are available on ISIS.

Zoom-Link:

Nov 16, 2020 12:00 PM Amsterdam, Berlin, Rome, Stockholm, Vienna

Every week on Mon, 16 occurrence(s)

Join Zoom Meeting

https://tu-berlin.zoom.us/j/66183667186?pwd=KzRDQUcrWDRLQVdaRkZRcXdqbVdkZz09

Meeting ID: 661 8366 7186

Passcode: 638230

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.

Under the common assumption that P≠NP, approximation algorithms are, in some sense, the best algorithms with polynomial time running time one can hope to design. Moreover, the performance guarantee α of an algorithm serves as a natural metric to compare the hardness of different problems. In this course, we will review many classical results in the field of approximation algorithms, highlighting different techniques commonly used for the design of such algorithms.

(non-exhaustive) list of covered topics:

• Greedy Algorithms & Local Search
• Rounding Data & Dynamic Programming
• Deterministic Rounding of Linear Programs (LPs)
• Random Sampling and Randomized Rounding of LPs
• Randomized Rounding of Semidefinite Programs (SDPs)
• Primal-Dual Method
• Hardness of Approximation

Prerequisites:

Students wishing to enroll for this course are expected to have taken the ADM I and ADM II courses, or to have a good knowledge of linear programming and basic knowledge in discrete optimization. 

The classes are given by Guillaume Sagnol.

Office hours:  on demand

Due to the COVID-19 pandemics, the lecture takes place online. Short Videos will be posted on ISIS.

A weekly online appointment will take place on Mondays from 12:00 to 13:00, via the Zoom-Software. The link is indicated at the top of this page and on ISIS. We will use this slot for FAQ-sessions, to discuss additional aspects of the course material, and to solve some exercises.

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

• David P. Williamson, David B. Shmoys, The Design of Approximation Algorithms, 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