Algorithme d'approximation

algorithme qui calcule une valeur approchée du résultat recherché

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éfinitionsModifier

ApproximationModifier

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  , un algorithme d'approximation de facteur   (i.e. un algorithme  -approché) est un algorithme donnant une solution de valeur  , avec la garantie que  .

Schéma d'approximationModifier

Un schéma d'approximation est un algorithme prenant comme entrée les données du problèmes mais aussi une valeur   et calculant une solution approchée avec un facteur  . Si le temps de calcul est polynomial en la taille de l'entrée et en  , on parle de schéma d'approximation en temps polynomial (abrégé PTAS en anglais)[1].

ExempleModifier

 
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 algorithmiquesModifier

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.

Difficulté d'approximationModifier

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 simplesModifier

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

Techniques avancéesModifier

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.

HistoriqueModifier

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]. 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[6].

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

Notes et référencesModifier

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, [détail de l’édition], chap. 35.
  2. David P. Williamson et David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press
  3. Voir (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 5 (« k-center »)
  4. a b et c (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 1.4 (« Introduction : Notes ») p. 10.
  5. Paul Erdős, « Gráfok páros körüljárású részgráfjairól (On bipartite subgraphs of graphs, in Hungarian), », Mat. Lapok, vol. 18,‎ , p. 283-288
  6. László Lovász, « On the ratio of optimal integral and fractional covers », Discrete mathematics, vol. 13, no 4,‎ , p. 383-390