En informatique et en recherche opérationnelle , les algorithmes d'approximation sont des algorithmes efficaces qui trouvent des solutions approchées aux problèmes d'optimisatio...
Worldlex WikiFrancaisLecture gratuite
En informatique et en recherche opérationnelle , les algorithmes d'approximation sont des algorithmes efficaces qui trouvent des solutions approchées aux problèmes d'optimisation (en particulier les problèmes NP-difficiles ) avec des garanties démontrables sur la distance de la solution retournée à la solution optimale. Les algorithmes d'approximation apparaissent naturellement en informatique théorique comme une conséquence de la conjecture largement admise P ≠ NP . Selon cette conjecture, une vaste classe de problèmes d'optimisation ne peut être résolue exactement en temps polynomial . Le domaine des algorithmes d'approximation cherche donc à comprendre avec quelle précision il est possible d'approcher les solutions optimales de ces problèmes en temps polynomial. Dans la grande majorité des cas, la garantie de ces algorithmes est multiplicative, exprimée par un rapport ou un facteur d'approximation : la solution optimale est toujours garantie d'être à un facteur multiplicatif (prédéterminé) de la solution retournée. Cependant, de nombreux algorithmes d'approximation offrent également une garantie additive sur la qualité de la solution retournée. Un exemple d'algorithme d'approximation avec garantie multiplicative est l' algorithme de Christofides-Serdyukov pour le problème du voyageur de commerce . Il fournit un parcours du voyageur de commerce dans une métrique dont la longueur est au plus égale à 3/2 fois celle du plus court parcours de ce type. Un exemple classique d'algorithme d'approximation offrant une garantie additive est la preuve constructive du théorème de Vizing . Elle montre comment colorier les arêtes d'un graphe non orienté avec au plus
La conception et l'analyse des algorithmes d'approximation reposent fondamentalement sur une démonstration mathématique certifiant la qualité des solutions renvoyées dans le pire des cas. Ceci les distingue des heuristiques telles que le recuit simulé ou les algorithmes génétiques , qui trouvent des solutions raisonnablement bonnes pour certaines entrées, mais ne fournissent aucune indication claire au départ quant à leurs chances de succès ou d'échec.
En informatique théorique, on s'intéresse de près à la compréhension des limites d'approximation de certains problèmes d'optimisation célèbres. Par exemple, l'une des questions ouvertes de longue date en informatique est de déterminer s'il existe un algorithme plus performant que la 2-approximation du problème de la forêt de Steiner proposée par Agrawal et al. . La volonté d'appréhender les problèmes d'optimisation difficiles sous l'angle de l'approximation est motivée par la découverte de liens mathématiques surprenants et de techniques largement applicables pour la conception d'algorithmes destinés à ces problèmes. Un exemple bien connu est l' algorithme de Goemans-Williamson pour la coupe maximale , qui résout un problème de théorie des graphes à l'aide d'un programme semi-défini issu du premier niveau de la hiérarchie des sommes de carrés .
Introduction
Un exemple simple d'algorithme d'approximation est celui du problème de la couverture minimale de sommets , où l'objectif est de choisir le plus petit ensemble de sommets tel que chaque arête du graphe d'entrée contienne au moins un sommet choisi. Une méthode pour trouver une couverture de sommets consiste à répéter le processus suivant : trouver une arête non couverte, ajouter ses deux extrémités à la couverture, et supprimer du graphe toutes les arêtes incidentes à l'un ou l'autre de ces sommets. Comme toute couverture de sommets du graphe d'entrée doit utiliser un sommet distinct pour couvrir chaque arête considérée (puisqu'elle forme un couplage ), la couverture obtenue est donc au plus deux fois plus grande que la couverture optimale. Autrement dit, il s'agit d'un algorithme d'approximation à facteur constant de 2. Sous la conjecture récente des jeux uniques , ce facteur est même le plus petit possible.
Les problèmes NP-difficiles varient considérablement en termes d'approximation ; certains, comme le problème du sac à dos , peuvent être approchés à un facteur multiplicatif près.et produisent donc des solutions arbitrairement proches de l'optimum (une telle famille d'algorithmes d'approximation est appelée schéma d'approximation en temps polynomial ou PTAS). D'autres problèmes sont impossibles à approcher à un facteur constant, voire polynomial, près, sauf si P = NP , comme dans le cas du problème de la clique maximale . Par conséquent, l'un des principaux avantages de l'étude des algorithmes d'approximation est une classification fine de la difficulté des différents problèmes NP-difficiles, au-delà de celle offerte par la théorie de la NP-complétude . Autrement dit, bien que les problèmes NP-complets puissent être équivalents (après réduction en temps polynomial) du point de vue des solutions exactes, les problèmes d'optimisation correspondants se comportent très différemment du point de vue des solutions approchées.
Techniques de conception d'algorithmes
Il existe aujourd'hui plusieurs techniques éprouvées pour concevoir des algorithmes d'approximation. En voici quelques exemples.
Techniques de programmation mathématique. Il s'agit de modéliser le problème considéré à l'aide d'une formulation de programmation mathématique appropriée (généralement une programmation convexe ), telle que la programmation linéaire ou la programmation semi-définie , afin d'obtenir un ensemble de solutions. Des techniques algorithmiques spécifiques à ces formulations sont ensuite appliquées.
Méthodes d'arrondi. Elles consistent à résoudre le problème considéré pour obtenir une solution fractionnaire satisfaisante, puis à la convertir en une solution entière. Parmi les techniques d'arrondi classiques, on trouve l'arrondi par seuil, l'arrondi aléatoire , garanties a posteriori
Bien que les algorithmes d'approximation fournissent toujours une garantie a priori dans le pire des cas (qu'elle soit additive ou multiplicative), ils offrent parfois également une garantie a posteriori souvent bien meilleure. C'est fréquemment le cas pour les algorithmes qui résolvent une relaxation convexe du problème d'optimisation sur les données d'entrée. Par exemple, un autre algorithme d'approximation pour la couverture minimale de sommets résout une relaxation de programmation linéaire afin de trouver une couverture de sommets dont la valeur est au plus le double de celle de la relaxation. Puisque la valeur de la relaxation ne dépasse jamais la taille de la couverture optimale, on obtient ainsi un autre algorithme d'approximation à un facteur 2. Bien que similaire à la garantie a priori de l'algorithme d'approximation précédent, la garantie de ce dernier peut être nettement supérieure (notamment lorsque la valeur de la relaxation linéaire est très éloignée de la taille de la couverture optimale).
Dureté de l'approximation
Le domaine de recherche des algorithmes d'approximation est étroitement lié à la théorie de l'inapproximabilité et s'en inspire. Cette théorie démontre, par réduction , la non-existence d'algorithmes efficaces avec certains rapports d'approximation (sous des hypothèses largement admises, telles que la conjecture P ≠ NP). Dans le cas du problème du voyageur de commerce métrique, le résultat d'inapproximabilité le plus connu exclut les algorithmes dont le rapport d'approximation est inférieur à 123/122 ≈ 1,008196, sauf si P = NP (Karpinski, Lampis, Schmied . Conjugué à l'existence de l'algorithme d'approximation de Christofides (rapport d'approximation 1,5), ce résultat indique que le seuil d'approximabilité pour le problème du voyageur de commerce métrique (s'il existe) se situe entre 123/122 et 1,5.
Bien que des résultats d'inapproximabilité aient été démontrés depuis les années 1970, ces résultats ont été obtenus de manière empirique et sans compréhension systématique à l'époque. Ce n'est qu'avec le résultat de Feige, Goldwasser, Lovász, Safra et Szegedy en 1990 sur l'inapproximabilité de l' ensemble indépendant et le célèbre théorème PCP [ des outils modernes pour démontrer des résultats d'inapproximabilité ont été mis au point. Le théorème PCP, par exemple, montre que les algorithmes d'approximation de Johnson (1974) pour Max SAT , la couverture d'ensembles , l'ensemble indépendant et la coloration atteignent tous le rapport d'approximation optimal, sous l'hypothèse P ≠ NP
aspect pratique
pour un
Structure des algorithmes d'approximation
Étant donné un problème d'optimisation :
où
et l'ensemble des solutions réalisables :
trouver la meilleure solution
Étant donné une solution réalisable
Plus précisément, avoir
pour un problème de minimisation :
pour un problème de maximisation :
On peut démontrer que l'approximation est optimale ( approximation précise ) en prouvant qu'il existe des cas où l'algorithme atteint la limite d'approximation, ce qui indique la précision de la borne. Dans ce cas, il suffit de construire une instance d'entrée conçue pour contraindre l'algorithme à un scénario défavorable.
Garanties de performance
Pour certains algorithmes d'approximation, il est possible de démontrer certaines propriétés concernant l'approximation du résultat optimal. Par exemple, un algorithme d'approximation ρ, A, est défini comme un algorithme pour lequel il a été démontré que la valeur/le coût, f ( x ), de la solution approchée A ( x ) pour une instance x ne sera pas supérieur (ou inférieur, selon le cas) à un facteur ρ multiplié par la valeur, OPT, d'une solution optimale.
1;\\ ho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }} ho <1.\fin{cas
Le facteur ρ est appelé garantie de performance relative . Un algorithme d'approximation possède une garantie de performance absolue , ou erreur bornée c , s'il a été prouvé pour toute instance x que
De même, la garantie de performance , R ( x,y ), d'une solution y à une instance x est définie comme
où f ( y ) représente la valeur/le coût de la solution y pour l'instance x . La garantie de performance est clairement supérieure ou égale à 1 et égale à 1 si et seulement si y est une solution optimale. Si un algorithme A garantit de retourner des solutions avec une garantie de performance d'au plus r ( n ), alors A est dit être un algorithme d'approximation r ( n ) et possède un facteur d'approximation de r ( n ). De même, un problème admettant un algorithme d'approximation r ( n ) est dit r ( n ) -approximable ou possède un facteur d'approximation de r ( n ).
Pour les problèmes de minimisation, les deux garanties différentes donnent le même résultat et pour les problèmes de maximisation, une garantie de performance relative de ρ est équivalente à une garantie de performance de
La garantie de performance absolue
C'est-à-dire que
Autrement dit, il est équivalent au ratio de performance absolue , avec une limite inférieure n sur la taille des instances du problème. Ces deux types de ratios sont utilisés car il existe des algorithmes pour lesquels la différence entre eux est significative.
termes Epsilon
Dans la littérature, le rapport d'approximation pour un problème de maximisation (minimisation) de c - ϵ (min : c + ϵ) signifie que l'algorithme possède un rapport d'approximation de c ∓ ϵ pour tout ϵ > 0, mais que ce rapport n'a pas (ou ne peut pas) être démontré pour ϵ = 0. Un exemple en est le rapport d'inapproximabilité optimal — inexistence d'approximation — de 7 / 8 + ϵ pour les instances satisfiables de MAX-3SAT, dû à Johan Håstad . Comme mentionné précédemment, lorsque c = 1, on dit que le problème admet un schéma d'approximation en temps polynomial .
Un terme ε peut apparaître lorsqu'un algorithme d'approximation introduit une erreur multiplicative et une erreur constante, tandis que l'optimum minimal des instances de taille n tend vers l'infini avec n . Dans ce cas, le rapport d'approximation est c ∓ k / OPT = c ∓ o(1) pour certaines constantes c et k . Pour tout ε > 0, on peut choisir N suffisamment grand tel que le terme k / OPT < ε pour tout n ≥ N. Pour tout ε fixé, les instances de taille n < N peuvent être résolues par force brute, démontrant ainsi l'existence d'algorithmes d'approximation avec garantie d'approximation — et donc d'un rapport d'approximation de c ∓ ε pour tout ε > 0.
Worldlex Wiki 
pour un
1;\\ ho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }} ho <1.\fin{cas