Nous présenterons les buts et les principes de la théorie de l'approximation polynomiale ainsi que ses principaux outils tels que les mesures de qualité (rapports classique et différentiel) et les réductions préservant l'approximation. Nous illustrerons tout ceci par des résultats d'approximation pour quelques problèmes connus d'optimisation combinatoire. Nous finirons en présentant quelques nouveaux aspects de la problématique de l'approximation polynomiale.

On présente quelques résultats antérieurs et questions ouvertes autour du problème suivant. Etant donné un graphe G=(V, E) et un entier positif D, trouver un ensemble d'arêtes de cardinalité minimum tel que le graphe augmenté G'=(V, E U E') soit biconnexe et de diamètre au plus D.

Adam L. Buchsbaum and Howard Karloff and Claire Kenyon and Nick Reingold and Mikkel Thorup

Dynamic Storage Allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L is the maximum sum of heights of rectangles that intersect any vertical line and OPT is the minimum height of the enclosing strip, it is obvious that OPT>L; previous work showed that OPT<3L. We continue the study of the relationship between OPT and L, proving that OPT=L+o(L) when the maximum job height is o(L).

En route, we construct several new polynomial-time approximation algorithms for in Dynamic Storage Allocation.