Ioan Todinca (LIFO - Université d'Orléans)

Motto: “ How strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search? “ Gödel, 1956

Je passerai en revue plusieurs techniques algorithmiques pour résoudre de façon exacte des problèmes d’optimisation NP-difficiles. Ces algorithmes seront de complexité exponentielle, le but étant néanmoins de donner les algorithmes les plus efficaces possible (la complexité est toujours mesurée au pire cas). Je présenterai des algorithmes pour résoudre des problèmes comme le voyageur de commerce (en temps 2 n ), coloration (en 3 n ), stable maximum (en 1.3 n ). Ces algorithmes utilisent des approches classiques (programmation dynamique, algorithmes récursifs de branchements) et moins classiques (notamment la technique “mesurer pour conquérir”). On évoquera d’autres méthodes (compression itérative, décompositions arborescentes) et des questions ouvertes.