Ebook: Algorithmes d’approximation

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.

---

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.

Content:
Front Matter....Pages I-XX
Introduction....Pages 1-11
Front Matter....Pages 13-13
Couverture par ensembles....Pages 15-27
L’arbre de Steiner et le voyageur de commerce....Pages 29-40
Coupe multis?paratrice et coupe en k morceaux....Pages 41-50
Coupe-cycles de sommets....Pages 51-58
Surfacteur minimum....Pages 59-66
Sac ? dos....Pages 67-73
Empaquetage....Pages 75-80
Minimisation du temps d’ex?cution total....Pages 81-85
Voyageur de commerce euclidien....Pages 87-91
Front Matter....Pages 93-99
Introduction ? la dualit? en programmation lin?aire....Pages 101-101
Alignement dual pour la couverture par ensembles....Pages 103-119
Arrondi en programmation lin?aire et couverture par ensembles....Pages 121-131
Sch?ma primal-dual et couverture par ensembles....Pages 133-139
Satisfaction maximum....Pages 141-146
Ordonnancement h?t?rog?ne....Pages 147-155
Multicoupe et multiflot entier dans un arbre....Pages 157-162
Coupe multis?paratrice....Pages 163-171
Multicoupe dans les graphes....Pages 173-186
Front Matter....Pages 187-199
Coupe la moins dense....Pages 101-101
For?t de Steiner....Pages 201-220
R?seau de Steiner....Pages 221-237
Placement d’installations....Pages 239-259
Programmation semi-d?finie....Pages 261-272
Front Matter....Pages 273-286
Vecteur le plus court....Pages 287-301
Probl?mes de d?nombrement....Pages 303-303
Difficult? de l’approximation....Pages 305-325
Probl?mes ouverts....Pages 327-339
Back Matter....Pages 341-369
....Pages 371-381