查看文章

Puisqu’il semble maintenant improbable que l’on puisse trouver un algorithme polynomial résolvant de façon exacte un problème NP-difficile, l’utilisation d’algorithmes polynomiaux retournant des solutions non optimales s’ est généralisée. Cependant, il est souhaitable que la qualité des solutions retournées ne soit pas trop dégradée et on demande donc à ces algorithmes d’approximation de donner une garantie sur leurs performances. Cette qualité est le plus souvent mesurée grâce au rapport d’approximation en pire cas.

Le vertex cover1 est un problème" classique" de minimisation, NP-complet pour lequel de nombreux algorithmes d’approximation ont été proposés. Par exemple, il est connu que l’algorithme ED, qui sélectionne les sommets d’un couplage maximal du graphe, possède un rapport d’approximation de 2 et l’algorithme MDG, qui sélectionne un sommet de degré maximum, le retire du graphe et recommence tant qu’il existe une arête, possède un rapport d’approximation de H (∆)= 1+ 1