Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 11 Janvier 2011

Algorithmes exacts pour les problèmes NP-difficiles

par 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 2n), coloration (en 3n), stable maximum (en 1.3n). 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr