Les ans du LIPN Analyse d'algorithmesNP et approximation

Les 20 ans du LIPN
Analyse d’algorithmesNP et approximation
pour le meilleur et pour le pire
OCAD
Sophie Toulouse
sophie.toulouse@lipn.univ-paris13.fr
LIPN, UMR 7030
Les 20 ans du LIPN – p. 1/25Plan
Introduction
•
Problèmes difficiles d’optimisation combinatoire
Les 20 ans du LIPN – p. 2/25Plan
Introduction
•
Problèmes difficiles d’optimisation combinatoire
Approximation
•
Analyse pire cas... garantie ?
•
Différentiel... résistances ?
Les 20 ans du LIPN – p. 2/25Plan
Introduction
•
Problèmes difficiles d’optimisation combinatoire
Approximation
•
Analyse pire cas... garantie ?
•
Différentiel... résistances ?
Analyse en moyenne
•
Généralisation du cadre d’étude
•
Définition de nouveaux outils d’analyse
Les 20 ans du LIPN – p. 2/25Plan
Introduction
•
Problèmes difficiles d’optimisation combinatoire
Approximation
•
Analyse pire cas... garantie ?
•
Différentiel... résistances ?
Analyse en moyenne
•
Généralisation du cadre d’étude
•
Définition de nouveaux outils d’analyse
Résolution effective
•
Algorithmes efficaces (solution, bornes)
•
Intégration à des schémas de résolution exacte (pilotage)
Les 20 ans du LIPN – p. 2/25Plan
Introduction
•
Problèmes difficiles d’optimisation combinatoire
Approximation
•
Analyse pire cas... garantie ?
•
Différentiel... résistances ?
Analyse en moyenne
•
Généralisation du cadre d’étude
•
Définition de nouveaux outils d’analyse
Résolution effective
•
Algorithmes efficaces (solution, bornes)
•
Intégration à des schémas de résolution exacte (pilotage)
Conclusion
Les 20 ans du LIPN – p. 2/25Introduction -NP Optimisation
Π : opt{f(s)|s∈S},S discret.
Les 20 ans du LIPN – p. 3/25Introduction -NP Optimisation
Π : opt{f(s)|s∈S},S discret.
•
NP : déciders∈S polynomial, calculerf(s) polynomial
Les 20 ans du LIPN – p. 3/25Introduction -NP Optimisation
Π : opt{f(s)|s∈S},S discret.
•
NP : déciders∈S polynomial, calculerf(s) polynomial
∗ ∗
•
Optimisation : on cherches telle quef(s ) est optimale surS
Les 20 ans du LIPN – p. 3/25Introduction -NP Optimisation
Π : opt{f(s)|s∈S},S discret.
•
NP : déciders∈S polynomial, calculerf(s) polynomial
∗ ∗
•
Optimisation : on cherches telle quef(s ) est optimale surS
Problèmes
Les 20 ans du LIPN – p. 3/25