algorithme d'approximation

CONT: Les problèmes d'optimisation NP-difficiles ne sont pas tous équivalents en termes ""d'approximabilité"" : certains [...] peuvent être approximés avec un facteur quelconque, la complexité en temps de l'algorithme d'approximation augmentant lorsque le facteur d'erreur diminue [...]
CONT: En informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristique garantissant à la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à une constante, par rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème.

CONT: An approximate algorithm is a way of dealing with NP-completeness for optimization problems, [although this] technique does not guarantee the best solution. The goal of an approximation algorithm is to come as close as possible to the optimum value in a reasonable amount of time which is at most polynomial time.