Algorithmes d'approximation
par Vijay V. Vazirani
Traduction de Nicolas Schabanel, ISBN 2-287-00677-X

Enfin paru en mars 2006 chez Springer !

Premiers chapitres disponibles en ligne : .pdf

Table des matières :

1 Introduction
1.1 Minorer OPT
1.2 Problèmes bien caractérisés et relations min-max
1.3 Exercices
1.4 Notes

Première partie – Algorithmes combinatoires

2 Couverture par ensembles
2.1 L’algorithme glouton
2.2 La méthode du mille-feuille
2.3 Application au problème du surfacteur minimum
2.4 Exercices
2.5 Notes

3 L’arbre de Steiner et le voyageur de commerce
3.1 L’arbre de Steiner métrique
3.2 Le voyageur de commerce métrique
3.3 Exercices
3.4 Notes

4 Coupe multiséparatrice et coupe en k morceaux
4.1 Le problème de la coupe multiséparatrice
4.2 Coupe en k morceaux de poids minimum
4.3 Exercices
4.4 Notes

5 k-Centre
5.1 élagage paramétré appliqué au k-centre métrique
5.2 k-Centre métrique pondéré
5.3 Exercices
5.4 Notes

6 Coupe-cycles de sommets
6.1 Graphes pondérés cyclomatiques
6.2 Coupe-cycles par la technique du mille-feuille
6.3 Exercices
6.4 Notes

7 Surfacteur minimum
7.1 Une 4-approximation
7.2 Réduction à 3 du facteur d’approximation
7.3 Exercices
7.4 Notes

8 Sac à dos
8.1 Un algorithme pseudo-polynomial pour le sac à dos
8.2 Un FPTAS pour le sac à dos
8.3 Existence de FPTAS et NP-difficulté forte
8.4 Exercices
8.5 Notes

9 Empaquetage
9.1 Un PTAS asymptotique
9.2 Exercices
9.3 Notes

10 Minimisation du temps d’exécution total
10.1 Une 2-approximation
10.2 Un PTAS pour le temps d’exécution minimum
10.3 Exercices
10.4 Notes

11 Voyageur de commerce euclidien
11.1 L’algorithme
11.2 Correction de l’algorithme
11.3 Exercices
11.4 Notes

Deuxième partie – Programmation linéaire en algorithmique

12 Introduction à la dualité en programmation linéaire
12.1 Le théorème de dualité en programmation linéaire
12.2 Relations min-max et dualité en programmation linéaire
12.3 Deux techniques algorithmiques fondamentales
12.4 Exercices
12.5 Notes

13 Alignement dual pour la couverture par ensembles
13.1 Analyse de l’algorithme glouton pour la couverture par ensembles par alignement dual
13.2 Variantes de la couverture par ensembles
13.3 Exercices
13.4 Notes

14 Arrondi en programmation linéaire et couverture
par ensembles
14.1 Un algorithme d’arrondi simple
14.2 Arrondi randomisé
14.3 Solutions demi-entières pour la couverture par sommets
14.4 Exercices
14.5 Notes

15 Schéma primal-dual et couverture par ensembles
15.1 Présentation générale du schéma primal-dual
15.2 Couverture par ensembles via le schéma primal-dual
15.3 Exercices
15.4 Notes

16 Satisfaction maximum
16.1 Traitement des grandes clauses
16.2 Dérandomisation par la méthode de l’espérance conditionnelle
16.3 Traitement des petites clauses par arrondi
16.4 Une 3/4-approximation
16.5 Exercices
16.6 Notes

17 Ordonnancement hétérogène
17.1 élagage paramétré et programmation linéaire
17.2 Propriétés des solutions extrémales
17.3 L’algorithme
17.4 Propriétés particulières des solutions extrémales
17.5 Exercices
17.6 Notes

18 Multicoupe et multiflot entier dans un arbre
18.1 Les problèmes et leurs relaxations
18.2 Algorithme primal-dual
18.3 Exercices
18.4 Notes

19 Coupe multiséparatrice
19.1 Une relaxation intéressante
19.2 Algorithme à base d’arrondi randomisé
19.3 Demi-intégralité de la coupe de nœuds multiséparatrice
19.4 Exercices
19.5 Notes

20 Multicoupe dans les graphes
20.1 Multiflot total maximum
20.2 Algorithme à base d’arrondi
20.3 Une instance critique
20.4 Quelques applications du problème de la multicoupe
20.5 Exercices
20.6 Notes

21 Coupe la moins dense
21.1 Multiflot sur demande
21.2 Formulation par programmation linéaire
21.3 Métriques, empaquetages de coupes et plongements l1
21.4 Plongement l1 de faible distorsion d'une métrique
21.5 Algorithme par arrondi
21.6 Applications
21.7 Exercices
21.8 Notes

22 Forêt de Steiner
22.1 La relaxation linéaire et son dual
22.2 Schéma primal-dual synchronisé
22.3 Analyse
22.4 Exercices
22.5 Notes

23 Réseau de Steiner
23.1 Relaxation linéaire et solutions demi-entières
23.2 La technique de l’arrondi répété
23.3 Caractérisation des solutions extrémales
23.4 Un argument de dénombrement
23.5 Exercices
23.6 Notes

24 Placement d’installations
24.1 Une interprétation intuitive du dual
24.2 Relaxation des conditions primales des écarts
complémentaires
24.3 Algorithme primal-dual
24.4 Analyse
24.5 Exercices
24.6 Notes

25 k-Médiane
25.1 Relaxation et dual
25.2 Principe de l’algorithme
25.3 Arrondi randomisé
25.4 Relaxation lagrangienne et algorithmes d’approximation
25.5 Exercices
25.6 Notes

26 Programmation semi-définie
26.1 Programmation quadratique stricte et programmation vectorielle
26.2 Matrices semi-définies positives
26.3 Programmation semi-définie
26.4 Approximation par arrondi randomisé
26.5 Améliorer la garantie pour MAX-2SAT
26.6 Exercices
26.7 Notes

Troisième partie – Autres sujets d’étude

27 Vecteur le plus court
27.1 Bases, déterminants et défaut d’orthogonalité
27.2 Les algorithmes d’Euclide et de Gauss
27.3 Minorer OPT par l’orthogonalisation de Gram-Schmidt
27.4 Algorithme en dimension n
27.5 Le module dual et ses applications algorithmiques
27.6 Exercices
27.7 Notes

28 Problèmes de dénombrement
28.1 Dénombrement des solutions DNF
28.2 Fiabilité d’un réseau
28.3 Exercices
28.4 Notes

29 Difficulté de l’approximation
29.1 Réductions, écart et facteur d’approximation limites
29.2 Le théorème PCP
29.3 Difficulté de l’approximation de MAX-3SAT
29.4 Difficulté de MAX-3SAT avec un nombre d’occurrences borné
29.5 Difficulté de la couverture par sommets et de l’arbre de Steiner
29.6 Difficulté de l’approximation de Clique
29.7 Difficulté de l’approximation de la couverture par ensembles
29.8 Exercices
29.9 Notes

30 Problèmes ouverts
30.1 Problèmes ayant un algorithme à un facteur constant
30.2 Autres problèmes d’optimisation
30.3 Problèmes de dénombrement
30.4 Notes

Annexes

A Éléments de théorie de la complexité
A.1 Certificats et classe NP
A.2 Réductions et NP-complétude
A.3 Problèmes d’optimisation NP et algorithmes d’approximation
A.4 Classes de complexité randomisées
A.5 Auto-réductibilité
A.6 Notes

B Éléments de théorie des probabilités
B.1 Espérance et moments
B.2 Déviations de la moyenne
B.3 Lois de probabilités classiques
B.4 Notes

Bibliographie
Index des problèmes
Index
Glossaire des mots anglais