Algorithmes d'approximation
Cours de base (30 h de cours, 30h de TD)
Cours : Nicolas Schabanel (Nicolas.Schabanel)
TD : Emmanuelle Lebhar (Emmanuelle Lebhar)
Ce cours présente la thématique de l'approximation en
algorithmique. Ce point est central en informatique puisque la
plupart des problèmes d'optimisation "réels" sont NP-difficiles et
donc présumés insolubles exactement en temps "raisonnable". Nous
aborderons différents aspects de la discipline, principalement:
- Conception et analyse des performances d'algorithmes
d'approximation:
- méthodes combinatoires, programmation linéaire et
semi-définie, analyse compétitive, randomisation, tour des problèmes
principaux du domaine...
- Classes de complexité de problèmes inapproximables:
- application
du théorème PCP, réductions ("généralisation" de la NP-difficulté),
exemples...
Tout au long de ce cours, nous nous efforcerons de faire apparaître la
généricité des méthodes présentées.
Plan détaillé prévisionnel
- Introduction et méthodes combinatoires:
- bornes inférieures,
garantie de performance, classes d'algorithmes, premiers exemples
(vertex cover, euclidean TSP,...), études des problèmes classiques importants
(Steiner tree, TSP, Cuts,...).
- Programmation linéaire et semi-définie:
- méthode de l'arrondi
aléatoire, programmation semi-définie, dualité, éventuellement
dérandomisation.
- Schémas d'approximation:
- Principes et exemples d'approximations
à e près (par exemple pour les problèmes suivants:
binpacking, knapsack, euclidean Max-Cut, euclidean TSP).
- Algorithmes en-ligne:
- analyse compétitive, application aux
problèmes d'ordonnancement et de placements.
- Classes de complexité:
- Théorème PCP et applications, Réduction
préservant l'inapproximabilité, Inapproximabilité de Max-3SAT, TSP
et Max-Clique.
Bibliographie
- V. Vazirani. Approximation algorithms. Springer, 1998.
- M. Atallah. Algorithms and theory of computation
handbook. CRC Press, 1999.
- A. Borodin, R. El-Yaniv. Online computation and
competitive analysis. Cambridge University Press, 1998.