par Vazirani, Vijay V.
Springer
-
-
Disponible - 518 VAZ
Etage 3 - Santé, Sciences et Techniques - Sciences
Résumé
Présente simplement des questions algorithmiques complexes à l'aide de démonstrations intuitives illustrées d'exemples. S'adresse aux scientifiques et aux étudiants travaillant dans le milieu de l'informatique, de la recherche opérationnelle ou des mathématiques discrètes.
- Éditeur(s)
-
Date
- DL 2006
-
Notes
- Bibliogr. p. 399-415. Index
-
Langues
- Français
- , traduit de : Anglais
-
Description matérielle
- 1 vol. (XX-427 p.) : ill., couv. ill. en coul. ; 24 cm
- Collections
- Titre(s) en relation
- Sujet(s)
-
ISBN
- 2-287-00677-X ;
- 978-2-287-00677-7
-
Indice
- 518 Calcul et analyse numériques
-
Quatrième de couverture
-
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.
-
-
Tables des matières
-
Algorithmes d'approximation
Vijay V. Vazirani
Springer
- 1 Introduction 1
- 1.1 Minorer OPT2
- 1.2 Problèmes bien caractérisés et relations min-max5
- 1.3 Exercices8
- 1.4 Notes11
- Première partie - Algorithmes combinatoires
- 2 Couverture par ensembles 15
- 2.1 L'algorithme glouton16
- 2.2 La méthode du mille-feuille17
- 2.3 Application au problème du surfacteur minimum20
- 2.4 Exercices23
- 2.5 Notes27
- 3 L'arbre de Steiner et le voyageur de commerce 29
- 3.1 L'arbre de Steiner métrique29
- 3.2 Le voyageur de commerce métrique32
- 3.3 Exercices36
- 3.4 Notes40
- 4 Coupe multiséparatrice et coupe en k morceaux 41
- 4.1 Le problème de la coupe multiséparatrice42
- 4.2 Coupe en k morceaux de poids minimum43
- 4.3 Exercices47
- 4.4 Notes50
- 5 k-Centre 51
- 5.1 Élagage paramétré appliqué au k-centre métrique51
- 5.2 k-Centre métrique pondéré54
- 5.3 Exercices56
- 5.4 Notes58
- 6 Coupe-cycles de sommets 59
- 6.1 Graphes pondérés cyclomatiques59
- 6.2 Coupe-cycles par la technique du mille-feuille62
- 6.3 Exercices65
- 6.4 Notes66
- 7 Surfacteur minimum 67
- 7.1 Une 4-approximation67
- 7.2 Réduction à 3 du facteur d'approximation71
- 7.3 Exercices73
- 7.4 Notes73
- 8 Sac à dos 75
- 8.1 Un algorithme pseudo-polynomial pour le sac à dos76
- 8.2 Un FPTAS pour le sac à dos77
- 8.3 Existence de FPTAS et NP-difficulté forte78
- 8.4 Exercices79
- 8.5 Notes80
- 9 Empaquetage 81
- 9.1 Un PTAS asymptotique82
- 9.2 Exercices84
- 9.3 Notes85
- 10 Minimisation du temps d'exécution total 87
- 10.1 Une 2-approximation87
- 10.2 Un PTAS pour le temps d'exécution minimum88
- 10.3 Exercices91
- 10.4 Notes91
- 11 Voyageur de commerce euclidien 93
- 11.1 L'algorithme93
- 11.2 Correction de l'algorithme96
- 11.3 Exercices98
- 11.4 Notes99
- Deuxième partie - Programmation linéaire en algorithmique
- 12 Introduction à la dualité en programmation linéaire 103
- 12.1 Le théorème de dualité en programmation linéaire103
- 12.2 Relations min-max et dualité en programmation linéaire107
- 12.3 Deux techniques algorithmiques fondamentales111
- 12.4 Exercices114
- 12.5 Notes119
- 13 Alignement dual pour la couverture par ensembles 121
- 13.1 Analyse de l'algorithme glouton pour la couverture par ensembles par alignement dual121
- 13.2 Variantes de la couverture par ensembles125
- 13.3 Exercices129
- 13.4 Notes131
- 14 Arrondi en programmation linéaire et couverture par ensembles 133
- 14.1 Un algorithme d'arrondi simple133
- 14.2 Arrondi randomisé134
- 14.3 Solutions demi-entières pour la couverture par sommets136
- 14.4 Exercices137
- 14.5 Notes139
- 15 Schéma primal-dual et couverture par ensembles 141
- 15.1 Présentation générale du schéma primal-dual141
- 15.2 Couverture par ensembles via le schéma primal-dual143
- 15.3 Exercices145
- 15.4 Notes146
- 16 Satisfaction maximum 147
- 16.1 Traitement des grandes clauses148
- 16.2 Dérandomisation par la méthode de l'espérance conditionnelle148
- 16.3 Traitement des petites clauses par arrondi150
- 16.4 Une 3/4-approximation152
- 16.5 Exercices154
- 16.6 Notes155
- 17 Ordonnancement hétérogène 157
- 17.1 Élagage paramétré et programmation linéaire157
- 17.2 Propriétés des solutions extrémales159
- 17.3 L'algorithme160
- 17.4 Propriétés particulières des solutions extrémales160
- 17.5 Exercices162
- 17.6 Notes162
- 18 Multicoupe et multiflot entier dans un arbre 163
- 18.1 Les problèmes et leurs relaxations163
- 18.2 Algorithme primal-dual166
- 18.3 Exercices169
- 18.4 Notes171
- 19 Coupe multiséparatrice 173
- 19.1 Une relaxation intéressante173
- 19.2 Algorithme à base d'arrondi randomisé175
- 19.3 Demi-intégralité de la coupe de noeuds multiséparatrice178
- 19.4 Exercices181
- 19.5 Notes185
- 20 Multicoupe dans les graphes 187
- 20.1 Multiflot total maximum188
- 20.2 Algorithme à base d'arrondi189
- 20.3 Une instance critique195
- 20.4 Quelques applications du problème de la multicoupe196
- 20.5 Exercices197
- 20.6 Notes199
- 21 Coupe la moins dense 201
- 21.1 Multiflot sur demande201
- 21.2 Formulation par programmation linéaire202
- 21.3 Métriques, empaquetage de coupes et plongements l1204
- 21.4 Plongement l1 de faible distorsion d'une métrique208
- 21.5 Algorithme par arrondi213
- 21.6 Applications214
- 21.7 Exercices218
- 21.8 Notes219
- 22 Forêt de Steiner 221
- 22.1 La relaxation linéaire et son dual221
- 22.2 Schéma primal-dual synchronisé222
- 22.3 Analyse227
- 22.4 Exercices230
- 22.5 Notes237
- 23 Réseau de Steiner 239
- 23.1 Relaxation linéaire et solutions demi-entières239
- 23.2 La technique de l'arrondi répété243
- 23.3 Caractérisation des solutions extrémales245
- 23.4 Un argument de dénombrement248
- 23.5 Exercices251
- 23.6 Notes258
- 24 Placement d'installations 261
- 24.1 Une interprétation intuitive du dual262
- 24.2 Relaxation des conditions primales des écarts complémentaires263
- 24.3 Algorithme primal-dual264
- 24.4 Analyse265
- 24.5 Exercices268
- 24.6 Notes272
- 25 k-Médiane 273
- 25.1 Relaxation et dual273
- 25.2 Principe de l'algorithme274
- 25.3 Arrondi randomisé277
- 25.4 Relaxation lagrangienne et algorithmes d'approximation281
- 25.5 Exercices282
- 25.6 Notes285
- 26 Programmation semi-définie 287
- 26.1 Programmation quadratique stricte et programmation vectorielle287
- 26.2 Matrices semi-définies positives289
- 26.3 Programmation semi-définie290
- 26.4 Approximation par arrondi randomisé292
- 26.5 Améliorer la garantie pour MAX-2SAT296
- 26.6 Exercices297
- 26.7 Notes301
- Troisième partie - Autres sujets d'étude
- 27 Vecteur le plus court 305
- 27.1 Bases, déterminants et défaut d'orthogonalité306
- 27.2 Les algorithmes d'Euclide et de Gauss308
- 27.3 Minorer OPT par l'orthogonalisation de Gram-Schmidt310
- 27.4 Algorithme en dimension n312
- 27.5 Le module dual et ses applications algorithmiques317
- 27.6 Exercices321
- 27.7 Notes325
- 28 Problèmes de dénombrement 327
- 28.1 Dénombrement des solutions DNF328
- 28.2 Fiabilité d'un réseau330
- 28.3 Exercices335
- 28.4 Notes338
- 29 Difficulté de l'approximation 341
- 29.1 Réductions, écart et facteur d'approximation limites341
- 29.2 Le théorème PCP344
- 29.3 Difficulté de l'approximation de MAX-3SAT347
- 29.4 Difficulté de MAX-3SAT avec un nombre d'occurrences borné349
- 29.5 Difficulté de la couverture par sommets et de l'arbre de Steiner351
- 29.6 Difficulté de l'approximation de Clique354
- 29.7 Difficulté de l'approximation de la couverture par ensembles358
- 29.8 Exercices366
- 29.9 Notes368
- 30 Problèmes ouverts 371
- 30.1 Problèmes ayant un algorithme à un facteur constant371
- 30.2 Autres problèmes d'optimisation373
- 30.3 Problèmes de dénombrement376
- 30.4 Notes381
- Annexes
- A Éléments de théorie de la complexité 385
- A.1 Certificats et classe NP385
- A.2 Réductions et NP-complétude386
- A.3 Problèmes d'optimisation NP et algorithmes d'approximation388
- A.4 Classes de complexité randomisées390
- A.5 Auto-réductibilité391
- A.6 Notes394
- B Éléments de théorie des probabilités 395
- B.1 Espérance et moments395
- B.2 Déviations de la moyenne396
- B.3 Lois de probabilités classiques397
- B.4 Notes398
- Bibliographie 399
- Index des problèmes 417
- Index 421
- Glossaire des mots anglais 425
-
-
Origine de la notice:
- BNF
-
Disponible - 518 VAZ
Etage 3 - Santé, Sciences et Techniques - Sciences
