Inroduction influence des parametres Problemes algorithmes parametres Complexite parametree et approximation

Christophe Paul

Description

Inroduction - influence des parametres Problemes, algorithmes parametres Complexite parametree et approximation Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345) Christophe PAUL (CNRS - LIRMM) November 4, 2008 Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)

• complexite parametree


• inroduction - influence des parametres problemes


• parametre specifique au probleme


• algorithmes parametres


• fixed-parameter algorithms


• croissance exponentielle du temps de calcul

Sujets

• Fellows
• Complexité paramétrée

Informations

• Publié par: pefav
• Nombre de lectures: 28
• Langue: Français

Extrait

Inroduction - in uence des parametres Problemes, algorithmes parametres Complexite parametree et approximation
Introduction a la complexite parametree (1)
(Complexite avancee - UMIN 345)
Christophe PAUL
(CNRS - LIRMM)
November 4, 2008
Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)Inroduction - in uence des parametres Problemes, algorithmes parametres Complexite parametree et approximation
Bibliographie
Parameterized Complexity, R. Downey and M. Fellows, 1999.
Invitation to Fixed-Parameter Algorithms, R. Niedermeier,
2006.
Parameterized Complexity Theory, J. Flum and M. Grohe,
2006.
Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)Inroduction - in uence des parametres Problemes, algorithmes parametres Complexite parametree et approximation
1 Inroduction - in uence des parametres
2 Problemes, algorithmes parametres
3 Complexite parametree et approximation
Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)\L’idee fondamentale est de restreindre l’explosion combinatoire,
semble-t-il inevitable, qui est responsable de la croissance
exponentielle du temps de calcul, a un parametre speci que au
probleme. . . "
R. Niedermeier
Inroduction - in uence des parametres Problemes, algorithmes parametres Complexite parametree et approximation
\Mesurer la complexite seulement en fonction de la taille de la
donnee signi e ignorer tout information structurelle sur l’instance
donnee. . . "
J. Flum and M. Grohe
Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)Inroduction - in uence des parametres Problemes, algorithmes parametres Complexite parametree et approximation
\Mesurer la complexite seulement en fonction de la taille de la
donnee signi e ignorer tout information structurelle sur l’instance
donnee. . . "
J. Flum and M. Grohe
\L’idee fondamentale est de restreindre l’explosion combinatoire,
semble-t-il inevitable, qui est responsable de la croissance
exponentielle du temps de calcul, a un parametre speci que au
probleme. . . "
R. Niedermeier
Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)2 nombre de variables : n = nombre de variables
nIl y a 2 a ectations possibles
nSi on se restreint a 3-sat, la complexite tombe a O(1; 49 )
3 nombre de clauses : m = nombre de clauses
mOn obtient une complexite en O(1; 24 )
4 longueur de la formule : l = nombre total de litteraux
lOn obtient une complexite en O(1; 08 )
5 structure de la formule : parametres bases par exemple sur
la structure du graphe de dependances. . .
Inroduction - in uence des parametres Problemes, algorithmes parametres Complexite parametree et approximation
L’exemple de sat
Mesure de la complexite en fonction de di erents parametres:
1 taille des clauses : k = nombre max. de litteraux par clause
k = 2: sat2 P
k > 3: sat2 NP-complet
Christophe PAUL (CNRS - LIRMM) Introduction a la complexite parametree (1) (Complexite avancee - UMIN 345)