Algorithmes d'approximation

Vijay V. Vazirani - Collection IRIS

430 pages, parution le 03/08/2010

Ajouter à une liste

Indisponible

Résumé

Le champ des algorithmes d'approximation est aujourd'hui l'un des domaines de recherche les plus actifs en informatique. Il allie la profondeur de la théorie mathématique aux promesses d'applications pratiques d'un intérêt considérable.

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-difficiles. 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 approchées à ces problèmes ont été développés. Une quantité considérable de résultats nouveaux a été établie lors de la dernière décennie et a révolutionné ce champ d'étude.

Le défi relevé par cet ouvrage est de présenter clairement les théories et méthodologies sous-jacentes sans rien ôter à la beauté des résultats. Ce livre expose ces questions algorithmiques complexes en proposant des démonstrations simples et intuitives accompagnées de nombreux exemples.

Sommaire

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
Vecteur le plus court
Problèmes de dénombrement
Difficulté de l'approximation
Problèmes ouverts
Annexes
Bibliographie
Index des problèmes
Index
Glossaire des mots anglais

Voir tout

Replier

Caractéristiques techniques

	PAPIER
Éditeur(s)	Springer
Auteur(s)	Vijay V. Vazirani
Collection	IRIS
Parution	03/08/2010
Nb. de pages	430
Format	15,5 x 23,5
Couverture	Broché
Poids	765g
Intérieur	Noir et Blanc
EAN13	9782287006777
ISBN13	978-2-287-00677-7