Approximation polynomiale des problèmes NP-difficiles
Optima locaux et rapport différentiel
Jérôme Monnot/Vangelis T. Paschos/Sophie Toulouse
Hermes Science
Avant-propos9
Chapitre 1. Introduction17
Chapitre 2. L'approximation polynomiale21
2.1. Les problèmes21
2.1.1. Qu'est-ce qu'un problème de NPO ?21
2.1.2. Définitions indispensables23
2.2. Leur résolution23
2.2.1. La mission de l'approximation polynomiale26
2.2.2. Son arme27
2.3. L'évaluation de leurs algorithmes27
2.3.1. Fer de lance de l'approximation polynomiale : le rapport classique27
2.3.2. Une alternative : le rapport différentiel28
2.3.3. L'erreur29
2.4. Degrés d'approximation30
2.4.1. Approximation à rapport constant r030
2.4.2. Approximation à r, r aussi proche de 1 que l'on veut32
2.5. Définition logique35
2.5.1. Les classes MaxNP et MaxSNP36
2.5.2. Logique et approximation38
2.6. Effets de classe41
2.6.1. Le principe de réduction41
2.6.1.1. Réduction polynomiale41
2.6.1.2. Réduction préservant l'optimalité42
2.6.1.3. Réduction préservant l'approximation43
2.6.2. La notion de complétude46
2.6.3. La fermeture47
2.7. Affinité entre problèmes47
2.7.1. Réductions continues47
2.7.2. Réductions affines50
2.8. Voyageur de commerce et affinité54
2.8.1. Le cas métrique55
2.8.2. Ses cousins55
2.8.3. Le cas bivalué56
2.8.4. Le cas général57
2.9. Conclusion58
Chapitre 3. Optimum local garanti61
3.1. Quelques concepts61
3.1.1. Qu'est-ce qu'un algorithme de recherche locale ?61
3.1.1.1. LSA - algorithme de recherche locale62
3.1.1.2. Complexité d'un LSA63
3.1.1.3. Conditions nécessaires et conditions suffisantes de polyno-mialité63
3.1.2. Voisinages h-bornés65
3.2. Les classes GLO[R]68
3.3. Exemples simples pour voisinages 1-bornés69
3.4. Limite des voisinages h-bornés72
3.5. Réductions préservant l'approximation locale73
3.5.1. Préserver le voisinage74
3.5.1.1. La LOC-réduction74
3.5.1.2. La LOC'-réduction77
3.5.2. La réduction dans GLO[R]79
3.5.3. Exemples80
3.6. GLO et associés première partie82
3.6.1. Voisinages miroirs et classe CGLO[R]82
3.6.2. Optima altérés et GGLO[R]84
3.6.3. Mixage ou GCGLO[R]84
Chapitre 4. Problèmes dans GLO et GLO[Delta]85
4.1. Des voisinages 1- et 2-bornés85
4.1.1. Couverture d'ensembles88
4.1.2. Ensemble minimum d'arêtes retour92
4.1.3. Couplage maximum dans un hypergraphe93
4.1.4. Les problèmes d'ordonnancement94
4.1.5. Le problème de sous-graphe partiel maximum libre de H095
4.1.6. Ensemble minimum de sommets retour98
4.2. Exemples pour les voisinages 3-bornés et plus99
4.2.1. Retour sur le problème de sous-graphe partiel maximum libre de H099
4.2.2. Le voyageur de commerce et le voisinage 2-opt104
4.3. Résultats négatifs107
4.3.1. Satisfaisabilité maximum107
4.3.2. Le sac-à-dos108
4.4. Où les classes GLO[R] se situent-elles ?110
4.4.1. GLO[R] et les classes d'approximation110
4.4.2. GLO[R] et les classes logiques115
4.4.3. Quelle unité dans tout ça ?117
4.5. Conclusion117
Chapitre 5. Les problèmes de satisfaisabilité121
5.1. Les problèmes de satisfaisabilité entre eux121
5.1.1. Présentation121
5.1.2. Tous pour un124
5.2. GLO et associés deuxième partie126
5.3. Déclinaison des problèmes de satisfaisabilité maximum en GLO128
5.3.1. Une opposition de plus entre rapports classique et différentiel128
5.3.2. MaxSat et CGLO129
5.3.3. MaxKappa-Sat et GLO129
5.3.4. MaxKappa-Sat et CGLO131
5.3.5. MaxNAEKappa-Sat et GLO132
5.3.6. MaxKappa-Sat et GCGLO133
5.4. Les problèmes de satisfaction de contraintes conjonctives134
5.4.1. Un problème difficile134
5.4.2. Vers le 1/4 différentiel138
5.4.3. Approximation à 1/3141
5.5. Limites de l'approche GLO142
5.5.1. 1/3, le meilleur de CGLO pour Max2-CCSP142
5.5.2. 1/5, le meilleur espoir de CGLO[Delta] pour Max2-CCSP145
5.5.3. 1/2, le meilleur de GLO pour MaxNAE2-Sat146
5.5.4. 1/3, le meilleur espoir de GLO[Delta] pour MaxNAE2-Sat147
5.6. Conclusion148
Chapitre 6. Réductions149
6.1. Dans les graphes et les hypergraphes (systèmes d'ensembles)149
6.1.1. Régularisation pour la couverture d'ensembles150
6.1.2. Dépondération pour la couverture d'ensembles151
6.1.3. Dépondération pour la couverture de sommets154
6.1.4. Autres problèmes simples dans les graphes156
6.2. Les problèmes de logique157
6.2.1. Autour de MinEQ157
6.2.2. Autour de MaxNAESat161
6.2.3. Dense ou pas dense ?164
6.3. Conclusion170
6.3.1. Un certain goût d'inachevé170
6.3.2. Synthèse170
Chapitre 7. En-deçà de GLO173
7.1. La classe PLS des problèmes de recherche locale173
7.1.1. De la difficulté de détermination des optima locaux174
7.1.1.1. Quelques notions indispensables174
7.1.1.2. Le graphe de transition175
7.1.2. Approximation des optima locaux177
7.2. Les problèmes radiaux178
7.2.1. Qu'est-ce que radial ?179
7.2.2. Les problèmes Tau-radiaux182
7.2.2.1. Définition et exemples183
7.2.2.2. Problèmes Tau-radiaux et optima locaux185
7.2.3. Une sous-famille remarquable186
7.2.3.1. Les problèmes réguliers186
7.2.3.2. Les problèmes héréditaires et anti-héréditaires188
7.2.3.3. Les problèmes de partitionnement héréditaire190
7.3. Conclusion190
Annexes191
A. Problèmes rencontrés191
A.1. Problèmes dans les graphes192
A.2. Problèmes de programmation linéaire197
A.3. Problèmes de logique198
A.4. Autres problèmes201
B. Définitions203
B.1. Les fondements203
B.2. Les classes205
B.2.1. Classes d'approximation205
B.2.2. Classes définies par la logique205
B.2.3. Classes d'approximation locale206
B.3. Réductions207
B.3.1. Propriétés remarquables207
B.3.2. Réductions remarquables208
B.4. Localité210
B.5. Problèmes particuliers210
Bibliographie213
Index219