Vazirani Algorithmes d'approximation

2006
ISBN: 978-2-287-31020-1
Verlag: Springer Paris
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Französisch, 448 Seiten, eBook

Reihe: Collection IRIS

Le champ des algorithmes d’approximation est aujourd’hui l’un des domaines de recherche les plus actifs en informatique. 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.

Zielgruppe

Research

Autoren/Hrsg.

Vazirani, Vijay V.

Inhaltsverzeichnis

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.– 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.