Approximation algorithms

Objective: 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.


  • 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 Appproximation


  • 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.