Algorithmes d’approximation

1. Introduction

Première partie. Algorithmes combinatoires

2. Couverture par ensembles

3. L’arbre de Steiner et le voyageur de commerce

4. Coupe multiséparatrice et coupe en k morceaux

5. k-Centre

6. Coupe-cycles de sommets

7. Surfacteur minimum

8. Sac à dos

9. Empaquetage

10. Minimisation du temps d’exécution total

11. Voyageur de commerce euclidien

Deuxième partie. Programmation linéaire en algorithmique

12. Introduction à la dualité en programmation linéaire

13. Alignement dual pour la couverture par ensembles

14. Arrondi en programmation linéaire et couverture par ensembles

15. Schéma primal-dual et couverture par ensembles

16. Satisfaction maximum

17. Ordonnancement hétérogène

18. Multicoupe et multiflot entier dans un arbre

19. Coupe multiséparatrice

20. Multicoupe dans les graphes

21. Coupe la moins dense

22. Forêt de Steiner

23. Réseau de Steiner

24. Placement d’installations

25. k-Médiane

26. Programmation semi-définie

Troisième partie. Autres sujets d’étude

27. Vecteur le plus court

28. Problèmes de dénombrement

29. Difficulté de l’approximation

30. Problèmes ouverts

DRM-restrictions

Printing: not available
Clipboard copying: not available

Keywords: COMPUTERS / Computer Science COM014000