Approximation algorithms
ECTS : 3
Volume horaire : 15
Description du contenu de l'enseignement :
The course surveys the fundamental concepts of polynomial approximation theory (design and analysis of approximation algorithms, inapproximability, approximation preserving reductions) as well as new approximation paradigms.
Compétence à acquérir :
- Links between decision-optimization problem
- Approximability classes (semantic - syntactic)
- Approximability/inapproximability of some paradigmatic combinatorial optimization problems (TSP, Vertex Cover, Set Cover, Independent Set/Clique, Coloring, Min and Max Satisfiability, Knapsack, etc.)
- Approximation preserving reductions and inapproximability
- New approximation paradigms: Moderately Exponential, Subexponential and Parameterized Approximation
Bibliographie, lectures recommandées :
- 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. Hochbaum, Approximation Algorithms for NP-Hard Problems, Course Technology, 1996.
- V. Th. Paschos, Complexité et Approximation Polynomiale, Hermès, 2004.
- V. Vazirani, Approximation Algorithms, Springer-Verlag, 2001.