Bien que cela puisse paraˆıtre paradoxal, toute science exacte
est domin´ee par la notion d’approximation.
Bertrand Russell (1872-1970)
La plupart des problèmes d’optimisation naturels sont NP-difficiles, et tout particulièrement ceux qui ont des applications réelles importantes. Suivant la conjecture largement admise P = NP, leur résolution exacte impliquerait un temps de calcul prohibitif. Caractériser la difficulté de l’approximation de ces problèmes par des algorithmes de temps polynomial est donc un sujet d’étude inévitable en informatique et en mathématiques. Cet ouvrage dresse un tableau de la théorie de l’algorithmique d’approximation à
ce jour. Il est raisonnable de penser que cette image évoluera dans le temps.
L’exposé se divise en trois parties. La première partie présente des algorithmes d’approximation combinatoires pour des problème fondamentaux en mettant en œuvre une grande diversité de techniques algorithmiques. La diversité de ces techniques peut paraˆıtre déconcertante au premier abord. La nature est en effet riche et nous ne pouvons pas espérer qu’un nombre limité d’astuces permette de résoudre la tr`es grande variété des problèmes NPdifficiles. Nous avons volontairement évité de trop catégoriser les différentes techniques, afin de ne pas restreindre leurs portées. Au contraire, nous avons tenté d’extraire aussi précisément que possible les caractéristiques individuelles de chaque problème, ainsi que les relations entre ces problèmes et les solutions algorithmiques proposées.
La deuxième partie est consacrée aux approximations reposant sur la programmation linéaire. Deux techniques fondamentales y sont présentées : la méthode de l’arrondi et la méthode primal-dual. La qualité de la solution approchée dépend principalement du programme linéaire choisi et de sa relaxation. Il n’y a pas de recette miracle pour trouver une bonne relaxation d’un problème, de mˆeme qu’il n’en existe pas pour démontrer un théorème
en mathématiques (les lecteurs familiers avec la théorie de la complexité reconnaˆıtront la question sous-jacente P = NP)........
Pour savoir plus :
Enregistrer un commentaire