Algorithmes d'approximation (Collection IRIS) (French Edition)

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 228700677X......Page 1 Sommaire......Page 14 1 Introduction......Page 20 1.1 Minorer OPT......Page 21 1.2 Problèmes bien caractérisés et relations min-max......Page 24 1.3 Exercices......Page 27 1.4 Notes......Page 30 Première partie – Algorithmes combinatoires......Page 31 2 Couverture par ensembles......Page 32 2.1 L'algorithme glouton......Page 33 2.2 La méthode du mille-feuille......Page 34 2.3 Application au problème du surfacteur minimum......Page 37 2.4 Exercices......Page 40 2.5 Notes......Page 44 3.1 L'arbre de Steiner métrique......Page 45 3.2 Le voyageur de commerce métrique......Page 48 3.3 Exercices......Page 52 3.4 Notes......Page 56 4 Coupe multiséparatrice et coupe en k morceaux......Page 57 4.1 Le problème de la coupe multiséparatrice......Page 58 4.2 Coupe en k morceaux de poids minimum......Page 59 4.3 Exercices......Page 63 4.4 Notes......Page 66 5.1 Élagage paramétré appliqué au k-centre métrique......Page 67 5.2 k-Centre métrique pondéré......Page 70 5.3 Exercices......Page 72 5.4 Notes......Page 74 6.1 Graphes pondérés cyclomatiques......Page 75 6.2 Coupe-cycles par la technique du mille-feuille......Page 78 6.3 Exercices......Page 81 6.4 Notes......Page 82 7.1 Une 4-approximation......Page 83 7.2 Réduction à 3 du facteur d'approximation......Page 87 7.4 Notes......Page 89 8 Sac à dos......Page 90 8.1 Un algorithme pseudo-polynomial pour le sac à dos......Page 91 8.2 Un FPTAS pour le sac à dos......Page 92 8.3 Existence de FPTAS et NP-difficulté forte......Page 93 8.4 Exercices......Page 94 8.5 Notes......Page 95 9 Empaquetage......Page 96 9.1 Un PTAS asymptotique......Page 97 9.2 Exercices......Page 99 9.3 Notes......Page 100 10.1 Une 2-approximation......Page 101 10.2 Un PTAS pour le temps d'exécution minimum......Page 102 10.4 Notes......Page 105 11.1 L'algorithme......Page 106 11.2 Correction de l'algorithme......Page 109 11.3 Exercices......Page 111 11.4 Notes......Page 112 Deuxième partie – Programmation linèaire en algorithmique......Page 113 12.1 Le théorème de dualité en programmation linéaire......Page 114 12.2 Relations min-max et dualité en programmation linéaire......Page 118 12.3 Deux techniques algorithmiques fondamentales......Page 122 12.4 Exercices......Page 125 12.5 Notes......Page 130 13.1 Analyse de l'algorithme glouton pour la couverture par ensembles par alignement dual......Page 131 13.2 Variantes de la couverture par ensembles......Page 135 13.3 Exercices......Page 139 13.4 Notes......Page 141 14.1 Un algorithme d'arrondi simple......Page 142 14.2 Arrondi randomisé......Page 143 14.3 Solutions demi-entières pour la couverture par sommets......Page 145 14.4 Exercices......Page 146 14.5 Notes......Page 148 15.1 Présentation générale du schéma primal-dual......Page 149 15.2 Couverture par ensembles via le schéma primal-dual......Page 151 15.3 Exercices......Page 153 15.4 Notes......Page 154 16 Satisfaction maximum......Page 155 16.2 Dérandomisation par la méthode de l'espérance conditionnelle......Page 156 16.3 Traitement des petites clauses par arrondi......Page 158 16.4 Une 3/4-approximation......Page 160 16.5 Exercices......Page 162 16.6 Notes......Page 163 17.1 Élagage paramétré et programmation linéaire......Page 164 17.2 Propriétés des solutions extrémales......Page 166 17.4 Propriétés particulières des solutions extrémales......Page 167 17.6 Notes......Page 169 18.1 Les problèmes et leurs relaxations......Page 170 18.2 Algorithme primal-dual......Page 173 18.3 Exercices......Page 176 18.4 Notes......Page 178 19.1 Une relaxation intéressante......Page 179 19.2 Algorithme à base d'arrondi randomisé......Page 181 19.3 Demi-intégralité de la coupe de nœuds multiséparatrice......Page 184 19.4 Exercices......Page 187 19.5 Notes......Page 191 20 Multicoupe dans les graphes......Page 193 20.1 Multiflot total maximum......Page 194 20.2 Algorithme à base d'arrondi......Page 195 20.3 Une instance critique......Page 201 20.4 Quelques applications du problème de la multicoupe......Page 202 20.5 Exercices......Page 203 20.6 Notes......Page 205 21.1 Multiflot sur demande......Page 206 21.2 Formulation par programmation linéaire......Page 207 21.3 Métriques, empaquetage de coupes et plongements l[sub(1)]......Page 209 21.4 Plongement l[sub(1)] de faible distorsion d'une métrique......Page 213 21.5 Algorithme par arrondi......Page 218 21.6 Applications......Page 219 21.7 Exercices......Page 223 21.8 Notes......Page 224 22.1 La relaxation linéaire et son dual......Page 226 22.2 Schéma primal-dual synchronisé......Page 227 22.3 Analyse......Page 232 22.4 Exercices......Page 235 22.5 Notes......Page 242 23.1 Relaxation linéaire et solutions demi-entières......Page 243 23.2 La technique de l'arrondi répété......Page 247 23.3 Caractérisation des solutions extrémales......Page 249 23.4 Un argument de dénombrement......Page 252 23.5 Exercices......Page 255 23.6 Notes......Page 262 24 Placement d'installations......Page 264 24.1 Une interprétation intuitive du dual......Page 265 24.2 Relaxation des conditions primales des écarts complémentaires......Page 266 24.3 Algorithme primal-dual......Page 267 24.4 Analyse......Page 268 24.5 Exercices......Page 271 24.6 Notes......Page 275 25.1 Relaxation et dual......Page 276 25.2 Principe de l'algorithme......Page 277 25.3 Arrondi randomisé......Page 280 25.4 Relaxation lagrangienne et algorithmes d'approximation......Page 284 25.5 Exercices......Page 285 25.6 Notes......Page 288 26.1 Programmation quadratique stricte et programmation vectorielle......Page 290 26.2 Matrices semi-définies positives......Page 292 26.3 Programmation semi-définie......Page 293 26.4 Approximation par arrondi randomisé......Page 295 26.5 Améliorer la garantie pour MAX-2SAT......Page 299 26.6 Exercices......Page 300 26.7 Notes......Page 304 Troisième partie – Autres sujets d'étude......Page 305 27 Vecteur le plus court......Page 306 27.1 Bases, déterminants et défaut d'orthogonalité......Page 307 27.2 Les algorithmes d'Euclide et de Gauss......Page 309 27.3 Minorer OPT par l'orthogonalisation de Gram-Schmidt......Page 311 27.4 Algorithme en dimension n......Page 313 27.5 Le module dual et ses applications algorithmiques......Page 318 27.6 Exercices......Page 322 27.7 Notes......Page 326 28 Problèmes de dénombrement......Page 327 28.1 Dénombrement des solutions DNF......Page 328 28.2 Fiabilité d'un réseau......Page 330 28.3 Exercices......Page 335 28.4 Notes......Page 338 29.1 Réductions, écart et facteur d'approximation limites......Page 340 29.2 Le théorème PCP......Page 343 29.3 Difficulté de l'approximation de MAX-3SAT......Page 346 29.4 Difficulté de MAX-3SAT avec un nombre d'occurrences borné......Page 348 29.5 Difficulté de la couverture par sommets et de l'arbre de Steiner......Page 350 29.6 Difficulté de l'approximation de Clique......Page 353 29.7 Difficulté de l'approximation de la couverture par ensembles......Page 357 29.8 Exercices......Page 365 29.9 Notes......Page 367 30.1 Problèmes ayant un algorithme à un facteur constant......Page 369 30.2 Autres problèmes d'optimisation......Page 371 30.3 Problèmes de dénombrement......Page 374 30.4 Notes......Page 379 Annexes......Page 380 A.1 Certificats et classe NP......Page 381 A.2 Réductions et NP-complétude......Page 382 A.3 Problèmes d'optimisation NP et algorithmes d'approximation......Page 384 A.4 Classes de complexité randomisées......Page 386 A.5 Auto-réductibilité......Page 387 A.6 Notes......Page 390 B.1 Espérance et moments......Page 391 B.2 Déviations de la moyenne......Page 392 B.3 Lois de probabilités classiques......Page 393 B.4 Notes......Page 394 Bibliographie......Page 395 C......Page 412 M......Page 413 V......Page 414 C......Page 415 L......Page 416 R......Page 417 Z......Page 418 F......Page 419 P......Page 420 Z......Page 421 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