Korte / Vygen Optimisation combinatoire

Theorie et algorithmes
2010
ISBN: 978-2-287-99037-3
Verlag: Springer Paris
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Französisch, Englisch, 663 Seiten, eBook

Reihe: Collection IRIS

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.

Zielgruppe

Professional/practitioner

Autoren/Hrsg.

Korte, Bernhard

Vygen, Jens

Weitere Mitwirkende

Fonlupt, Jean

Inhaltsverzeichnis

1;Préface;7
2;Avant-propos à la quatrième édition originale;8
3;Sommaire;9
4;Chapitre 1 Introduction;14
4.1;1.1 Énumération;15
4.2;1.2 Temps d’exécution des algorithmes;18
4.3;1.3 Problèmes d’optimisation linéaire;21
4.4;1.4 Tri;22
4.5;Exercices;24
4.6;Références;25
5;Chapitre 2 Graphes;26
5.1;2.1 Définitions fondamentales;26
5.2;2.2 Arbres, cycles, coupes;30
5.3;2.3 Connexité;38
5.4;2.4 Graphes eulériens et bipartis;45
5.5;2.5 Planarité;47
5.6;2.6 Dualité planaire;55
5.7;Exercices;58
5.8;Références;62
6;Chapitre 3 Programmation linéaire;64
6.1;3.1 Polyèdres;66
6.2;3.2 Algorithme du simplexe;69
6.3;3.3 Implémentation de l’algorithme du simplexe;72
6.4;3.4 Dualité;76
6.5;3.5 Enveloppes convexes et polytopes;80
6.6;Exercices;81
6.7;Références;84
7;Chapitre 4 Algorithmes de programmation linéaire;86
7.1;4.1 Taille des sommets et des faces;87
7.2;4.2 Fractions continues;89
7.3;4.3 Méthode d’élimination de Gauss;92
7.4;4.4 Méthode des ellipsoïdes;96
7.5;4.5 Théorème de Khachiyan;101
7.6;4.6 Séparation et optimisation;103
7.7;Exercices;110
7.8;Références;112
8;Chapitre 5 Programmation en nombres entiers;113
8.1;5.1 Enveloppe entière d’un polyèdre;115
8.2;5.2 Transformations unimodulaires;119
8.3;5.3 Totale duale-intégralité;121
8.4;5.4 Matrices totalement unimodulaires;124
8.5;5.5 Plans coupants;129
8.6;5.6 Relaxation lagrangienne;134
8.7;Exercices;136
8.8;Références;140
9;Chapitre 6 Arbres couvrants et arborescences;143
9.1;6.1 Arbre couvrant de poids minimum;144
9.2;6.2 Arborescence de poids minimum;150
9.3;6.3 Descriptions polyédrales;154
9.4;6.4 Empilements d’arbres et d’arborescences;157
9.5;Exercices;160
9.6;Références;164
10;Chapitre 7 Plus courts chemins;167
10.1;7.1 Plus courts chemins à partir d’une source;168
10.2;7.2 Plus courts chemins entre toutes les paires de sommets;173
10.3;7.3 Circuit moyen minimum;175
10.4;Exercices;177
10.5;Références;179
11;Chapitre 8 Flots dans les réseaux;182
11.1;8.1 Théorème flot-max/coupe-min;183
11.2;8.2 Théorème de Menger;187
11.3;8.3 Algorithme d’Edmonds-Karp;189
11.4;8.4 Flots bloquants et algorithme de Fujishige;191
11.5;8.5 Algorithme de Goldberg-Tarjan;193
11.6;8.6 Arbres de Gomory-Hu;198
11.7;8.7 Capacité d’une coupe dans un graphe non orienté;204
11.8;Exercices;206
11.9;Références;212
12;Chapitre 9 Flots de coût minimum;216
12.1;9.1 Formulation du problème;216
12.2;9.2 Un critère d’optimalité;218
12.3;9.3 Algorithme par élimination du circuit moyen minimum;221
12.4;9.4 Algorithme par plus courts chemins successifs;224
12.5;9.5 Algorithme d’Orlin;228
12.6;9.6 Algorithme network simplex;232
12.7;9.7 Flots dynamiques;236
12.8;Exercices;238
12.9;Références;242
13;Chapitre 10 Couplage maximum;245
13.1;10.1 Couplage dans les graphes bipartis;246
13.2;10.2 Matrice de Tutte;248
13.3;10.3 Théorème de Tutte;250
13.4;10.4 Décompositions en oreilles des graphes facteur-critiques;253
13.5;10.5 Algorithme du couplage d’Edmonds;259
13.6;Exercices;269
13.7;Références;272
14;Chapitre 11 Couplage avec poids;276
14.1;11.1 Problème d’affectation;277
14.2;11.2 Aperçu de l’algorithme du couplage avec poids;278
14.3;11.3 Implémentation de l’algorithme du couplage avec poids;281
14.4;11.4 Postoptimalité;295
14.5;11.5 Polytope du couplage;296
14.6;Exercices;300
14.7;Références;302
15;Chapitre 12 b-couplages et T-joints;304
15.1;12.1 b-couplages;304
15.2;12.2 T-joints de poids minimum;308
15.3;12.3 T-joints et T-coupes;312
15.4;12.4 Théorème de Padberg-Rao;315
15.5;Exercices;319
15.6;Références;322
16;Chapitre 13 Matroïdes;324
16.1;13.1 Systèmes d’indépendance et matroïdes;324
16.2;13.2 Autres axiomes;329
16.3;13.3 Dualité;333
16.4;13.4 Algorithme glouton;338
16.5;13.5 Intersection de matroïdes;343
16.6;13.6 Partition de matroïdes;348
16.7;13.7 Intersection de matroïdes avec poids;350
16.8;Exercices;354
16.9;Références;357
17;Chapitre 14 Généralisations des matroïdes;359
17.1;14.1 Greedoïdes;359
17.2;14.2 Polymatroïdes;363
17.3;14.3 Minimisation de fonctions sous-modulaires;368
17.4;14.4 Algorithme de Schrijver;370
17.5;14.5 Fonctions sous-modulaires symétriques;374
17.6;Exercices;376
17.7;Références;379
18;Chapitre 15 NP-complétude;382
18.1;15.1 Machines de Turing;383
18.2;15.2 Thèse de Church;385
18.3;15.3 P et NP;390
18.4;15.4 Théorème de Cook;395
18.5;15.5 Quelques problèmes NP-complets de base;399
18.6;15.6 Classe coNP;407
18.7;15.7 Problèmes NP-difficiles;409
18.8;Exercices;413
18.9;Références;417
19;Chapitre 16 Algorithmes d’approximation;419
19.1;16.1 Couverture par des ensembles;420
19.2;16.2 Problème de la coupe-max;426
19.3;16.3 Coloration;432
19.4;16.4 Schémas d’approximation;440
19.5;16.5 Satisfaisabilité maximum;443
19.6;16.6 Théorème PCP;448
19.7;16.7 L-réductions;453
19.8;Exercices;459
19.9;Références;463
20;Chapitre 17 Le problème du sac à dos;468
20.1;17.1 Sac à dos fractionnaire et problème du médian pondéré;468
20.2;17.2 Un algorithme pseudo-polynomial;471
20.3;17.3 Un schéma d’approximation entièrement polynomial;473
20.4;Exercices;476
20.5;Références;477
21;Chapitre 18 Le problème du bin-packing;479
21.1;18.1 Heuristiques gloutonnes;480
21.2;18.2 Un schéma d’approximation asymptotique;485
21.3;18.3 Algorithme de Karmarkar-Karp;490
21.4;Exercices;493
21.5;Références;495
22;Chapitre 19 Multiflots et chaînes arête-disjointes;497
22.1;19.1 Multiflots;498
22.2;19.2 Algorithmes pour le multiflot;501
22.3;19.3 Problème des chemins arc-disjoints;506
22.4;19.4 Problème des chaînes arête-disjointes;510
22.5;Exercices;516
22.6;Références;519
23;Chapitre 20 Problèmes de conception de réseaux;522
23.1;20.1 Arbres de Steiner;523
23.2;20.2 Algorithme de Robins-Zelikovsky;528
23.3;20.3 Conception de réseaux fiables;534
23.4;20.4 Un algorithme d’approximation primal-dual;538
23.5;20.5 Algorithme de Jain;546
23.6;Exercices;553
23.7;Références;556
24;Chapitre 21 Le problème du voyageur de commerce;560
24.1;21.1 Algorithmes d’approximation pour le PVC;560
24.2;21.2 Problème du voyageur de commerce euclidien;565
24.3;21.3 Méthodes locales;573
24.4;21.4 Polytope du voyageur de commerce;580
24.5;21.5 Bornes inférieures;586
24.6;21.6 Méthodes par séparation et évaluation;589
24.7;Exercices;591
24.8;Références;595
25;Chapitre 22 Le problème de localisation;599
25.1;22.1 Problème de localisation sans capacités;599
25.2;22.2 Solutions arrondies de la programmation linéaire;602
25.3;22.3 Méthodes primales-duales;604
25.4;22.4 Réduction d’échelle et augmentation gloutonne;609
25.5;22.5 Bornes du nombre d’installations;613
25.6;22.6 Recherche locale;617
25.7;22.7 Problèmes de localisation avec capacités;623
25.8;22.8 Problème de localisation universel;626
25.9;Exercices;633
25.10;Références;635
26;Notations;638
27;Index des noms d’auteurs;641
28;Index général;651

Graphes.- Programmation linéaire.- Algorithmes de programmation linéaire.- Programmation en nombres entiers.- Arbres couvrants et arborescences.- Plus courts chemins.- Flots dans les réseaux.- Flots de coût minimum.- Couplage maximum.- Couplage avec poids.- b-couplages et T-joints.- Matroïdes.- Généralisations des matroïdes.- NP-complétude.- Algorithmes d’approximation.- Le probléme du sac á dos.- Le probléme du bin-packing.- Multiflots et chaînes arête-disjointes.- Problémes de conception de réseaux.- Le probléme du voyageur de commerce.- Le probléme de localisation.