Algorithmes d'approximation
Coll. IRIS

La plupart des problèmes issus d'applications relevant de domaines aussi différents que la conception de circuits VLSI, la conception et la planification de réseaux, l'ordonnancement, la théorie des jeux, la biologie ou la théorie des nombres, sont des problèmes NP-complets. Leur résolution exacte demanderait des ressources informatiques inaccessibles et ne peut donc être envisagée. Pour faire face à cette situation, un grand nombre d'algorithmes proposant des solutions adaptées à ces problèmes ont été développés. L'objectif de cet ouvrage est de mettre en évidence le remarquable travail effectué et de présenter clairement les théories et méthodologies sous-jacentes.

Introduction. Couverture par ensembles. L'arbre de Steiner et le voyageur de commerce. Coupe multiséparatrice et coupe en k morceaux. k-Centre. Coupe-cycles de sommets. Surfacteur minimum. Sac à dos. Empaquetage. Minimisation du temps d'exécution total. Voyageur de commerce euclidien. Introduction à la dualité en programmation linéaire. Alignement dual pour la couverture par ensembles. Arrondi en programmation linéaire et couverture par Ensembles. Schéma primal-dual et couverture par ensembles. Satisfaction maximum. Ordonnancement hétérogène. Multicoupe et multiflot entier dans un arbre. Coupe multiséparatrice. Multicoupe dans les graphes. Coupe la moins dense. Forêt de Steiner. Réseau de Steiner. Placement d'installations. k-Médiane. Programmation semi-définie.