Algorithme d'approximation

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.

L'intérêt de tels algorithmes est qu'il est parfois plus facile de trouver une solution approchée qu'une solution exacte, le problème pouvant par exemple être NP-complet mais admettre un algorithme d'approximation polynomial. Ainsi, dans les situations où l'on cherche une bonne solution, mais pas forcément la meilleure, un algorithme d'approximation peut être un bon outil.

Définitions

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 $z^{*}$, un algorithme d'approximation de facteur $\rho >1$ (i.e. un algorithme $\rho$-approché) est un algorithme donnant une solution de valeur $z$, avec la garantie que $z\leq \rho z^{*}$.

Schéma d'approximation

Un schéma d'approximation est un algorithme prenant comme entrée les données du problèmes mais aussi une valeur $\epsilon >0$ et calculant une solution approchée avec un facteur $(1+\epsilon )$. Si le temps de calcul est polynomial en la taille de l'entrée pour chaque valeur $\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 $1/\epsilon$, on parle de schéma d'approximation en temps entièrement polynomial (abrégé FPTAS en anglais).

Exemple

Un exemple de tournée du voyageur de commerce en Allemagne.

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.

Techniques algorithmiques

Parmi les techniques utilisées, 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.

Difficulté d'approximation

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.

Exemples simples

Le problème du voyageur de commerce dans un graphe $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 $K_{V}$ où les arêtes de $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 $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.

Techniques avancées

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.

Historique

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

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