Algorithme d'approximation

Selon la nature du problème (maximisation, minimisation, etc.) la définition peut varier, on donne ici la définition classique pour un problème de minimisation avec facteur d'approximation constant.

Pour un problème de minimisation ayant une solution optimale de valeur ${\displaystyle z^{*}}$, un algorithme d'approximation de facteur ${\displaystyle \rho >1}$ (i.e. un algorithme ${\displaystyle \rho }$-approché) est un algorithme donnant une solution de valeur ${\displaystyle z}$, avec la garantie que ${\displaystyle z\leq \rho z^{*}}$.

Un schéma d'approximation est un algorithme prenant comme entrée les données du problèmes mais aussi une valeur ${\displaystyle \epsilon >0}$ et calculant une solution approchée avec un facteur ${\displaystyle (1+\epsilon )}$. Si le temps de calcul est polyomial en la taille de l'entrée pour chaque valeur ${\displaystyle \epsilon }$, on parle de schéma d'approximation en temps polynomial (abrégé PTAS en anglais). Si de plus, on demande que le temps de calcul soit aussi en ${\displaystyle 1/\epsilon }$, on parle de schéma d'approximation en temps entièrement polynomial (abrégé FPTAS en anglais)[1].

Le problème du voyageur de commerce dans un graphe ${\displaystyle G=(V,E)}$ avec des poids quelconques (positifs) est un problème qui n'admet pas d'algorithme d'approximation. En effet, tout algorithme d'approximation pour ce problème dans le graphe complet ${\displaystyle K_{V}}$ où les arêtes de ${\displaystyle E}$ ont une valeur nulle et les autres la valeur 1 fournit une réponse au problème de décision NP-complet de statuer sur l'hamiltonicité d'un graphe (en l'occurrence ${\displaystyle G}$ est hamiltonien si et seulement si l'algorithme approché fournit une solution de valeur nulle).

Un autre problème est le problème du k-centre métrique qui admet une réduction simple au problème de l'ensemble dominant[3].

Il existe des techniques plus complexes pour montrer des résultats de difficulté d'approximation. Elles tournent essentiellement autour du théorème PCP. Plus récemment la conjecture des jeux uniques a été utilisée pour montrer des résultats plus forts.