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. 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 . 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 polyomial en la taille de l'entrée pour chaque valeur , 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 , on parle de schéma d'approximation en temps entièrement polynomial (abrégé FPTAS en anglais). 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.