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 polynomial 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].

 

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. En affinant cette approche en utilisant un couplage bien choisi on peut aussi obtenir un facteur d'approximation de 3/2, avec l'algorithme de Christofides.

Parmi les techniques utilisées^[2], on compte les méthodes d'algorithmique classique, par exemple un algorithme glouton permet parfois d'obtenir une bonne approximation à défaut de calculer une solution optimale. On peut aussi citer des algorithmes de recherche locale et de programmation dynamique.

Beaucoup d'algorithmes sont basées sur l'optimisation linéaire. On peut par exemple arrondir une solution fractionnaire ou utiliser un schéma primal-dual. Une technique plus avancée est d'utiliser l'optimisation SDP, comme pour le problème de la coupe maximum.

Parmi les problèmes NP-complets certains sont dits difficile à approximer, c'est-à-dire qu'ils n'admettent pas d'algorithme d'approximation si l'on suppose certaines hypothèses, par exemple P différent de NP ou bien la conjecture des jeux uniques.

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.

Des algorithmes d'approximation ont été découverts avant même la mise en place de la théorie de la NP-complétude^[4], par exemple par Paul Erdős dans les années 1960, pour le problème de la coupe maximum^[5] ou Ronald Graham, pour les algorithmes d'ordonnancement ^[6],[7] . Cependant c'est à la suite de cette théorie que le domaine s'est vraiment développé^[4]. L'utilisation de l'optimisation linéaire est due à László Lovász dans les années 1970^[4], pour le problème de couverture par ensembles^[8].

Dans les années 1990, le théorème PCP a été une avancée très importante pour la non-approximabilité.

•   Portail de l'informatique théorique