Notice
Algorithmes d'approximation
Coll. IRIS
Auteur : VAZIRANI Vijay V.
Directeur de Collection : PUECH Nicolas
Langue : Français
Thèmes d'Algorithmes d'approximation :
Date de parution : 03-2006
Ouvrage 600 p. · Broché
Épuisé
ISBN : 9782287006777
Ouvrage 600 p. · Broché
Épuisé
ISBN : 9782287006777

· PDF : 51,00 €
·
Acheter l'e-book
Acheter l'e-book

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.
© 2019 LAVOISIER S.A.S.