Présentation du cours
Ce cours est une introduction avancée à l'algorithmique d'approximation.
La plupart des problèmes rencontrés dans la nature
sont NP-difficiles et ne peuvent donc pas être résolus exactement
en temps raisonnable (à moins que P
= NP).
Nous pouvons cependant dans certain concevoir des algorithmes qui
garantissent que la solution renvoyée a un coût raisonnable,
c.-à-d. proche du coût optimal. Nous abordons dans
ce cours :
- Conception et analyse des performances
d'algorithmes d'approximation :
- méthodes combinatoires
- programmation linéaire (dualité, relaxation,...)
- randomisation et dérandomisation
- schéma d'approximation
- applications aux problèmes classiques du
domaine
- Résultats d'inapproximabilités :
- preuves vérifiables stochastiquement (PCP)
- applications du théorème PCP aux problèmes
classiques
 The
lectures can be done in english upon request.
L'ouvrage de référence du domaine :
- V. Vazirani, Approximation
Algorithms. Springer, 2nde éd. (1ère éd.
2001), ISBN: 3-540-65367-8. (Traduction en français à paraître
1er semestre 2005)
Autres ouvrages utiles
- T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction
to Algorithms. MIT Press, 2nde éd. (2001), ISBN:
0-262-03293-7. Traduit en français par
X. Cazin et G.-L. Kocher, Dunod (2002), ISBN: 2-10-003922-9.
- D. Hochbaum (ed.), Approximation
algorithms for NP-hard problems. PWS publishing company
(1996), ISBN: 053494968-1.
- A.
Borodin, R. El-Yaniv. Online
computation and competitive analysis. Cambridge
University Press (1998), ISBN:0521619467.
Archives 2004-2005
Le cours (32h - 16 séances)
- Introduction : le représentant de commerce (TSP)
- Couverture par sommets et par ensembles (vertex cover et set
cover)
- k-Centre et la méthode de l'élagage
paramétré (k-center et parametric
prunning)
- Introduction aux probabilités discrètes
- Algorithmes randomisés et dérandomisation par
la méthode de l'espérance conditionnelle : Max-Cut
et Max-SAT
- Schémas d'approximation : FPTAS pour le sac-à-dos (knapsack) et
APTAS pour l'empaquetage (bin packing)
- Introduction à la dualité en programmation linéaire
- Max-SAT et la méthode de l'arrondi LP
- Schéma primal-dual : multi-coupe et multiflot dans
un arbre
- TD 1 Empaquetage et arbres de Steiner (.pdf)
01/10/04
- TD 2 La méthode du mille feuilles (.pdf)
15/10/04
- TD 3 Dominer, couvrir, colorier... (.pdf)
22/10/04
- TD 4 Après le centre, l'asymétrie (.pdf)
29/10/04
- TD 5 Indépendance et espérance (.pdf)
02/11/04
- TD 6 Forces et faiblesses de la randomisation (.pdf)
09/11/04
- TD 7 PTAS et sac-à-dos (.pdf)
03/12/04
- ...
Partiel et Examen
Archives 2003-2004
Le cours (32h - 16 séances)
- Introduction : le représentant de commerce (TSP)
- Couverture par sommets et par ensembles (vertex
cover et set
cover)
- k-Centre et la méthode de l'élagage paramétré (k-center et
parametric prunning)
- Algorithmes randomisés et dérandomisation par la méthode de
l'espérance conditionnelle : Max-Cut
- Schémas d'approximation : FPTAS pour le sac-à-dos (knapsack) et
APTAS pour l'empaquetage (bin packing)
- Introduction à la dualité en programmation linéaire
- La couverture par ensembles via l'alignement dual (set cover
via dual fitting)
- Max-SAT et la méthode de l'arrondi LP
- Schéma primal-dual : multi-coupe et multiflot dans un arbre
- Inapproximabilité : application du théorème PCP, pas de PTAS
pour Max-SAT
- TD 1 Travelling Salesman Problem et Arbre de Steiner (.pdf) 22/09/03
- TD 2 Couvertures et compagnie (.pdf) 29/09/03
- TD 3 Surfacteur minimum (.pdf) 06/10/03
- TD 4 Mille-feuille et k-centre (.pdf) 13/10/03
- TD 5 Coupe-circuits de sommets (.pdf) 20/10/03
- TD 6 Méthode de l'espérance conditionnelle (.pdf)
27/10/03
- TD 7 FPTAS et sac-à-dos (.pdf) 03/11/03
- TD 8 Minimisation du temps d'exécution total (.pdf) 12/11/03
- TD 9 Dualité en programmation linéaire (.pdf) 24/11/03
- TD 10 Arrondi LP et couverture par ensembles (.pdf) 01/12/03
- TD 11 Schéma primal-dual et ordonnancement hétérogène
(.pdf) 08/12/03
Partiel et Examen
- Partiel (.pdf)
et correction (.pdf)
17/11/03
- Examen (.pdf)
07/01/04
|
