Optimisation combinatoire: Theorie et algorithmes (Collection IRIS) (French Edition)

Ce livre est la traduction française de la quatrième et dernière édition de Combinatorial Optimization: Theory and Algorithms écrit par deux éminents spécialistes du domaine: Bernhard Korte et Jens Vygen de l'université de Bonn en Allemagne. Il met l’accent sur les aspects théoriques de l'optimisation combinatoire ainsi que sur les algorithmes efficaces et exacts de résolution de problèmes. Il se distingue en cela des approches heuristiques plus simples et souvent décrites par ailleurs. L’ouvrage contient de nombreuses démonstrations, concises et élégantes, de résultats difficiles. Destiné aux étudiants de Master et de Doctorat, ainsi qu’aux chercheurs en Mathématiques et Informatique, ce livre est considéré par la communauté scientifique comme un ouvrage de référence. Title Page......Page 2 Copyright Page......Page 5 Préface......Page 7 Avant-propos à la quatrième édition originale......Page 8 Table of Contents......Page 9 Chapitre 1 Introduction......Page 14 1.1 Énumération......Page 15 1.2 Temps d’exécution des algorithmes......Page 18 1.3 Problèmes d’optimisation linéaire......Page 21 1.4 Tri......Page 22 Exercices......Page 24 Références......Page 25 2.1 Définitions fondamentales......Page 26 2.2 Arbres, cycles, coupes......Page 30 2.3 Connexité......Page 38 2.4 Graphes eulériens et bipartis......Page 45 2.5 Planarité......Page 47 2.6 Dualité planaire......Page 55 Exercices......Page 58 Références......Page 62 Chapitre 3 Programmation linéaire......Page 64 3.1 Polyèdres......Page 66 3.2 Algorithme du simplexe......Page 69 3.3 Implémentation de l’algorithme du simplexe......Page 72 3.4 Dualité......Page 76 3.5 Enveloppes convexes et polytopes......Page 80 Exercices......Page 81 Références......Page 84 Chapitre 4 Algorithmes de programmation linéaire......Page 86 4.1 Taille des sommets et des faces......Page 87 4.2 Fractions continues......Page 89 4.3 Méthode d’élimination de Gauss......Page 92 4.4 Méthode des ellipsoïdes......Page 96 4.5 Théorème de Khachiyan......Page 101 4.6 Séparation et optimisation......Page 103 Exercices......Page 110 Références......Page 112 Chapitre 5 Programmation en nombres entiers......Page 113 5.1 Enveloppe entière d’un polyèdre......Page 115 5.2 Transformations unimodulaires......Page 119 5.3 Totale duale-intégralité......Page 121 5.4 Matrices totalement unimodulaires......Page 124 5.5 Plans coupants......Page 129 5.6 Relaxation lagrangienne......Page 134 Exercices......Page 136 Références......Page 140 Chapitre 6 Arbres couvrants et arborescences......Page 143 6.1 Arbre couvrant de poids minimum......Page 144 6.2 Arborescence de poids minimum......Page 150 6.3 Descriptions polyédrales......Page 154 6.4 Empilements d’arbres et d’arborescences......Page 157 Exercices......Page 160 Références......Page 164 Chapitre 7 Plus courts chemins......Page 167 7.1 Plus courts chemins à partir d’une source......Page 168 7.2 Plus courts chemins entre toutes les paires de sommets......Page 173 7.3 Circuit moyen minimum......Page 175 Exercices......Page 177 Références......Page 179 Chapitre 8 Flots dans les réseaux......Page 182 8.1 Théorème flot-max/coupe-min......Page 183 8.2 Théorème de Menger......Page 187 8.3 Algorithme d’Edmonds-Karp......Page 189 8.4 Flots bloquants et algorithme de Fujishige......Page 191 8.5 Algorithme de Goldberg-Tarjan......Page 193 8.6 Arbres de Gomory-Hu......Page 198 8.7 Capacité d’une coupe dans un graphe non orienté......Page 204 Exercices......Page 206 Références......Page 212 9.1 Formulation du problème......Page 216 9.2 Un critère d’optimalité......Page 218 9.3 Algorithme par élimination du circuit moyen minimum......Page 221 9.4 Algorithme par plus courts chemins successifs......Page 224 9.5 Algorithme d’Orlin......Page 228 9.6 Algorithme network simplex......Page 232 9.7 Flots dynamiques......Page 236 Exercices......Page 238 Références......Page 242 Chapitre 10 Couplage maximum......Page 245 10.1 Couplage dans les graphes bipartis......Page 246 10.2 Matrice de Tutte......Page 248 10.3 Théorème de Tutte......Page 250 10.4 Décompositions en oreilles des graphes facteur-critiques......Page 253 10.5 Algorithme du couplage d’Edmonds......Page 259 Exercices......Page 269 Références......Page 272 Chapitre 11 Couplage avec poids......Page 276 11.1 Problème d’affectation......Page 277 11.2 Aperçu de l’algorithme du couplage avec poids......Page 278 11.3 Implémentation de l’algorithme du couplage avec poids......Page 281 11.4 Postoptimalité......Page 295 11.5 Polytope du couplage......Page 296 Exercices......Page 300 Références......Page 302 12.1 b-couplages......Page 304 12.2 T-joints de poids minimum......Page 308 12.3 T-joints et T-coupes......Page 312 12.4 Théorème de Padberg-Rao......Page 315 Exercices......Page 319 Références......Page 322 13.1 Systèmes d’indépendance et matroïdes......Page 324 13.2 Autres axiomes......Page 329 13.3 Dualité......Page 333 13.4 Algorithme glouton......Page 338 13.5 Intersection de matroïdes......Page 343 13.6 Partition de matroïdes......Page 348 13.7 Intersection de matroïdes avec poids......Page 350 Exercices......Page 354 Références......Page 357 14.1 Greedoïdes......Page 359 14.2 Polymatroïdes......Page 363 14.3 Minimisation de fonctions sous-modulaires......Page 368 14.4 Algorithme de Schrijver......Page 370 14.5 Fonctions sous-modulaires symétriques......Page 374 Exercices......Page 376 Références......Page 379 Chapitre 15 NP-complétude......Page 382 15.1 Machines de Turing......Page 383 15.2 Thèse de Church......Page 385 15.3 P et NP......Page 390 15.4 Théorème de Cook......Page 395 15.5 Quelques problèmes NP-complets de base......Page 399 15.6 Classe coNP......Page 407 15.7 Problèmes NP-difficiles......Page 409 Exercices......Page 413 Références......Page 417 Chapitre 16 Algorithmes d’approximation......Page 419 16.1 Couverture par des ensembles......Page 420 16.2 Problème de la coupe-max......Page 426 16.3 Coloration......Page 432 16.4 Schémas d’approximation......Page 440 16.5 Satisfaisabilité maximum......Page 443 16.6 Théorème PCP......Page 448 16.7 L-réductions......Page 453 Exercices......Page 459 Références......Page 463 17.1 Sac à dos fractionnaire et problème du médian pondéré......Page 468 17.2 Un algorithme pseudo-polynomial......Page 471 17.3 Un schéma d’approximation entièrement polynomial......Page 473 Exercices......Page 476 Références......Page 477 Chapitre 18 Le problème du bin-packing......Page 479 18.1 Heuristiques gloutonnes......Page 480 18.2 Un schéma d’approximation asymptotique......Page 485 18.3 Algorithme de Karmarkar-Karp......Page 490 Exercices......Page 493 Références......Page 495 Chapitre 19 Multiflots et chaînes arête-disjointes......Page 497 19.1 Multiflots......Page 498 19.2 Algorithmes pour le multiflot......Page 501 19.3 Problème des chemins arc-disjoints......Page 506 19.4 Problème des chaînes arête-disjointes......Page 510 Exercices......Page 516 Références......Page 519 Chapitre 20 Problèmes de conception de réseaux......Page 522 20.1 Arbres de Steiner......Page 523 20.2 Algorithme de Robins-Zelikovsky......Page 528 20.3 Conception de réseaux fiables......Page 534 20.4 Un algorithme d’approximation primal-dual......Page 538 20.5 Algorithme de Jain......Page 546 Exercices......Page 553 Références......Page 556 21.1 Algorithmes d’approximation pour le PVC......Page 560 21.2 Problème du voyageur de commerce euclidien......Page 565 21.3 Méthodes locales......Page 573 21.4 Polytope du voyageur de commerce......Page 580 21.5 Bornes inférieures......Page 586 21.6 Méthodes par séparation et évaluation......Page 589 Exercices......Page 591 Références......Page 595 22.1 Problème de localisation sans capacités......Page 599 22.2 Solutions arrondies de la programmation linéaire......Page 602 22.3 Méthodes primales-duales......Page 604 22.4 Réduction d’échelle et augmentation gloutonne......Page 609 22.5 Bornes du nombre d’installations......Page 613 22.6 Recherche locale......Page 617 22.7 Problèmes de localisation avec capacités......Page 623 22.8 Problème de localisation universel......Page 626 Exercices......Page 633 Références......Page 635 Notations......Page 638 Index des noms d’auteurs......Page 641 Index général......Page 651 Cet ouvrage décrit de manière détaillée les résultats théoriques et les algorithmes efficaces de l'optimisation combinatoire. Il présente des démonstrations concises mais complètes de nombreux résultats dont certains n'avaient jamais été exposés auparavant. De la théorie des graphes à la programmation linéaire, des problèmes de mariage aux théories des matroïdes et de la complexité, le propos couvre l'ensemble des thématiques classiques et contemporaines de ce champ qui compte parmi les plus actifs des mathématiques discrètes. Cette traduction française de la quatrième édition anglaise (la plus récente à la date de publication) intègre les dernières corrections des auteurs ainsi que des développements récents sur de nombreux sujets. Véritable référence de l'optimisation combinatoire, ce livre s'adresse principalement aux étudiants en mathématiques et en informatique des 2e et 3e cycles universitaires, ainsi qu'aux ingénieurs et aux chercheurs confrontés à des problèmes d'optimisation