| Crédit : 3 ECTS |
| Langue du cours : anglais
|
|
|
|
Volume horaire
- CM :
15 h
- Volume horaire global (hors stage) :
15 h
Compétences à 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
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.
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.
Enseignant responsable
CRISTINA BAZGAN