Complexité des algorithmes exponentiels
Equipe OC
Membres : LIFO (Orléans), LORIA (Nancy), Laboratoire d’Informatique.
La théorie de la complexité a connu de nombreux développements depuis de nombreuses années, notamment en proposant des classes de complexité pour mesurer la complexité des problèmes. Relativement récemment, un intérêt est né pour l'étude de la complexité dans le pire des cas des algorithmes dît exponentiels, c'est-à-dire des algorithmes retournant une solution optimale à un problème mais requérant un temps de calcul exponentiel.
Deux axes de recherche ont été développés dans la littérature : le premier s'intéresse à l'établissement d'une borne de complexité globale dans le pire des cas pour les algorithmes exponentiels, tandis que le second s'intéresse à l'établissement d'une borne de complexité plus fine et qui dépend d'un paramètre du problème. Dans ce dernier cas on parle de complexité paramétrée.
Nous nous intéressons à ces deux types de problèmes. Dans le cas de la complexité dans le pire des cas globale, nous avons commencé, dans le cadre d'un projet (2008-2009) du GDR « Recherche Opérationnelle », à étudier comment les techniques qui existaient pour des problèmes d'optimisation combinatoire pouvaient être appliquées pour calculer la complexité dans le pire des cas de problèmes d'ordonnancement NP-difficiles. Dans le cas de la complexité paramétrée, nous avons commencé à travailler dans le cadre d'un projet (2008-2009) du GDR « Recherche Opérationnelle ».
Deux axes de recherche ont été développés dans la littérature : le premier s'intéresse à l'établissement d'une borne de complexité globale dans le pire des cas pour les algorithmes exponentiels, tandis que le second s'intéresse à l'établissement d'une borne de complexité plus fine et qui dépend d'un paramètre du problème. Dans ce dernier cas on parle de complexité paramétrée.
Nous nous intéressons à ces deux types de problèmes. Dans le cas de la complexité dans le pire des cas globale, nous avons commencé, dans le cadre d'un projet (2008-2009) du GDR « Recherche Opérationnelle », à étudier comment les techniques qui existaient pour des problèmes d'optimisation combinatoire pouvaient être appliquées pour calculer la complexité dans le pire des cas de problèmes d'ordonnancement NP-difficiles. Dans le cas de la complexité paramétrée, nous avons commencé à travailler dans le cadre d'un projet (2008-2009) du GDR « Recherche Opérationnelle ».