Abstract (EN)

Nous commençons par définir et motiver une notion de rapport d'approximation différentiel asymptotique. Pour cela, nous introduisons une classe de problèmes que nous appelons radiaux qui comprend en particulier les problèmes héréditaires. Puis nous validons la définition de rapport d'approximation différentiel asymptotique en établissant des résultats positifs, conditionnels et négatifs pour différents problèmes combinatoires. Nous proposons d'abord une analyse, dans le cadre de l'approximation différentielle, d'un algorithme glouton classique (le first fit decreasing ) pour le problème de bin packing. Nous traitons alors les problèmes de couverture minimum des sommets d'un graphe par des cliques induites et des arêtes d'un graphe biparti par des sous-graphes partiels bipartis complets et donnons une réduction préservant l'approximation différentielle du premier au second. Enfin, nous prouvons deux résultats négatifs concernant la possibilité d'approcher le problème de coloration des sommets d'un graphe par un schéma d'approximation différentiel polynomial.