Algorithmes exponentiels pour la résolution exacte et approchée de problèmes NP-difficiles
Institution:
Paris 9Disciplines:
Directors:
Abstract EN:
This thesis is a junction between two fields of complexity theory, namely exact computation and efficient approximation. We first design faster exponential algorithms for several NP-hard problems (maximum independent set, minimum independent dominating set, dominating clique, quasi independent set). Moreover, we introduce the "moderately exponential approximation" field, displaying fast (though exponential) approximation algorithms for many classical graph problems, such as : independent set, dominating set, edge and vertex coloring, traveling salesman, Steiner tree. . .
Abstract FR:
Cette thèse se situe à l'interface entre deux branches de la théorie de la complexité, la résolution exacte et l'approximation polynomiale. Nous développons dans un premier temps des algorithmes modérément exponentiels, capables de résoudre des problèmes fondamentaux de théorie des graphes (stable maximum, stable dominant mi-nimal, clique dominante, quasi-stable) de façon plus rapide que ceux existant jusqu'ici. Surtout, nous introduisons la notion d' approximation exponentielle , et exhibons des algorithmes exponentiels à garantie de performance plus rapides que les algorithmes exacts pour une large variété de problèmes classiques, parmi lesquels : stable maximum, domination, coloration de sommets ou d'arêtes, voyageur de commerce, arbre de Steiner. . .