Algorithmes d'approximation (Collection IRIS)

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