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.

Contents:

• 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

Bibliography

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