Algorithme d'approximation

Un article de Wikipédia, l'encyclopédie libre.

Un algorithme d'approximation est une heuristique garantissant à la qualité de la solution fournie 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.

Donc, pour toute instance d'un problème de minimisation admettant un algorithme d'approximation avec facteur $ρ > 1$ (i.e. un algorithme $ρ$ -approché), si $z *$ est la valeur de la solution optimale et $z$ la valeur de la solution donnée par l'algorithme d'approximation, on aura $z \le \rho z^*$ . C'est le cas par exemple pour le problème du transversal minimum puisque tout transversal formé par les sommets incidents aux arêtes d'un couplage maximal pour l'inclusion a une cardinalité inférieure à deux fois l'optimum. C'est aussi le cas pour le cas particulier du Voyageur de commerce où les poids satisfont les inégalités triangulaires car alors, le poids minimum d'un arbre couvrant est toujours inférieur à deux fois l'optimum.

Pour toute instance d'un problème de maximisation admettant un algorithme d'approximation avec facteur $0 < ρ < 1$ (on parle toujours d'algorithme $ρ$ -approché), si $z *$ est la valeur de la solution optimale et $z$ la valeur de la solution donnée par l'algorithme d'approximation, on aura $z \ge \rho z^*$ .

Parmi les problèmes NP-complets certains sont non-approximable, c'est-à-dire qu'ils n'admettent pas d'algorithme d'approximation. C'est le cas du Voyageur de commerce dans un graphe $G = (V, E)$ avec des poids quelconques (positifs) puisque tout algorithme d'approximation pour ce problème dans le graphe complet $K V$ où les arêtes de $E$ ont une valeur nulle et les autres une valeur infiniment grande fournit une réponse au problème de décision NP-complet de statuer sur l'Hamiltonicité d'un graphe (en l'occurrence $G$ est Hamitonien si et seulement si l'algorithme approché fournit une solution de valeur nulle).