Optimisation combinatoire 2: concepts avancés (Traité IC2, série Informatique et systèmes d'information)

Ce livre est dédié à des concepts avancés l'optimisation combinatoire, comme
l'approximation polynomiale et la robustesse des solutions et des algorithmes.
Ce sont des thématiques considérées aux frontières entre la recherche
opérationnelle et l'optimisation combinatoire, l'informatique théorique et les
mathématiques discrètes. Cet ouvrage est divisé en deux parties : éléments de
la théorie et techniques de l'approximation polynomiale et robustesse en
optimisation combinatoire. La première partie, dédiée à l'approximation
polynomiale, présente : les principes généraux de la théorie de
l'approximation polynomiale (approximabilité - inapproximabilité des
problèmes), les réductions préservant l'approximabilité des problèmes, et la
résolution exacte et approchée des problèmes combinatoires par la recherche
locale. La deuxième partie, dédiée à la robustesse, présente quelques-unes des
notions de robustesse de solutions en optimisation combinatoire : optimisation
combinatoire inverse, optimisation combinatoire probabiliste et algorithmique
on-line.