Algorithme d'approximation - Approximation algorithm

En informatique et en recherche opérationnelle , les algorithmes d'approximation sont des algorithmes efficaces qui trouvent des solutions approchées à des problèmes d'optimisation (en particulier des problèmes NP-difficiles ) avec des garanties prouvables sur la distance de la solution renvoyée à la solution optimale. Les algorithmes d'approximation apparaissent naturellement dans le domaine de l'informatique théorique à la suite de la conjecture P NP largement répandue . Sous cette conjecture, une large classe de problèmes d'optimisation ne peut pas être résolue exactement en temps polynomial . Le domaine des algorithmes d'approximation essaie donc de comprendre à quel point il est possible d'approcher des solutions optimales à de tels problèmes en temps polynomial. Dans une écrasante majorité des cas, la garantie de tels algorithmes est multiplicative exprimée sous la forme d'un rapport d'approximation ou d'un facteur d'approximation, c'est-à-dire que la solution optimale est toujours garantie d'être à l'intérieur d'un facteur multiplicatif (prédéterminé) de la solution renvoyée. Cependant, il existe également de nombreux algorithmes d'approximation qui fournissent une garantie supplémentaire sur la qualité de la solution renvoyée. Un exemple notable d'algorithme d'approximation qui fournit les deux est l'algorithme d'approximation classique de Lenstra , Shmoys et Tardos pour l' ordonnancement sur des machines parallèles indépendantes .

La conception et l'analyse d'algorithmes d'approximation impliquent de manière cruciale une preuve mathématique certifiant la qualité des solutions renvoyées dans le pire des cas. Cela les distingue des heuristiques telles que le recuit ou les algorithmes génétiques , qui trouvent des solutions raisonnablement bonnes sur certaines entrées, mais ne fournissent aucune indication claire au départ sur le moment où elles peuvent réussir ou échouer.

L' informatique théorique suscite un grand intérêt pour mieux comprendre les limites auxquelles on peut approcher 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 qui surpasse l' algorithme d'approximation 1.5 de Christofides au problème métrique du voyageur de commerce . Le désir de comprendre les problèmes d'optimisation difficiles du point de vue de l'approximation est motivé par la découverte de connexions mathématiques surprenantes et de techniques largement applicables pour concevoir des algorithmes pour les problèmes d'optimisation difficiles. Un exemple bien connu du premier est l' algorithme de Goemans-Williamson pour la coupe maximale , qui résout un problème de théorie des graphes en utilisant une géométrie de grande dimension.

introduction

Un exemple simple d'algorithme d'approximation est celui du problème de couverture de sommets minimum , 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 façon de trouver une couverture de sommet consiste à répéter le processus suivant : recherchez une arête non couverte, ajoutez ses deux extrémités à la couverture et supprimez toutes les arêtes incidentes à l'un des sommets du graphe. Comme toute couverture de sommets du graphe d'entrée doit utiliser un sommet distinct pour couvrir chaque arête considérée dans le processus (puisqu'elle forme une correspondance ), la couverture de sommets produite est donc au plus deux fois plus grande que la couverture optimale. En d'autres termes, il s'agit d'un algorithme d'approximation à facteur constant avec un facteur d'approximation de 2. Selon la récente conjecture des jeux uniques , ce facteur est même le meilleur possible.

Les problèmes NP-difficiles varient considérablement dans leur approximation; certains, comme le problème du sac à dos , peuvent être approchés à l'intérieur d'un facteur multiplicatif , pour tout fixe , 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 sont impossibles à approximer à l'intérieur d'un facteur constant, ou même polynomial, à moins que P = NP , comme dans le cas du problème de la clique maximale . Par conséquent, un avantage important de l'étude des algorithmes d'approximation est une classification fine de la difficulté de divers problèmes NP-difficiles au-delà de celle offerte par la théorie de la NP-complétude . En d'autres termes, bien que les problèmes NP-complets puissent être équivalents (sous des réductions de temps polynomiales) les uns aux autres 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. ${\style d'affichage 1+\epsilon }$${\displaystyle \epsilon >0}$

Techniques de conception d'algorithmes

À l'heure actuelle, il existe plusieurs techniques établies pour concevoir des algorithmes d'approximation. Ceux-ci incluent les suivants.

1. Algorithme gourmand
2. Recherche locale
3. Énumération et programmation dynamique
4. Résoudre une relaxation de programmation convexe pour obtenir une solution fractionnaire. Puis convertir cette solution fractionnaire en une solution réalisable par un arrondi approprié. Les relaxations populaires comprennent les suivantes.
   • Relaxations de programmation linéaire
   • Semidéfinie relaxations
5. Méthodes primales-duales
6. Raccord double
7. Intégrer le problème dans une métrique, puis résoudre le problème sur la métrique. Ceci est également connu sous le nom d'intégration métrique.
8. Échantillonnage aléatoire et utilisation du caractère aléatoire en général en conjonction avec les méthodes ci-dessus.

Garanties a posteriori

Alors que les algorithmes d'approximation fournissent toujours une garantie a priori dans le pire des cas (qu'elle soit additive ou multiplicative), dans certains cas, ils fournissent également une garantie a posteriori qui est souvent bien meilleure. C'est souvent le cas pour les algorithmes qui fonctionnent en résolvant une relaxation convexe du problème d'optimisation sur l'entrée donnée. Par exemple, il existe un algorithme d'approximation différent pour la couverture de sommets minimale qui résout une relaxation de programmation linéaire pour trouver une couverture de sommets qui est au plus deux fois la valeur de la relaxation. Étant donné que la valeur de la relaxation n'est jamais supérieure à la taille de la couverture de sommet optimale, cela donne un autre algorithme de 2-approximation. Bien que cela soit similaire à la garantie a priori de l'algorithme d'approximation précédent, la garantie de ce dernier peut être bien meilleure (en effet lorsque la valeur de la relaxation LP est loin de la taille de la couverture de sommet optimale).

Dureté d'approximation

Les algorithmes d'approximation en tant que domaine de recherche sont étroitement liés et informés par la théorie de l'inapproximation où la non-existence d'algorithmes efficaces avec certains rapports d'approximation est prouvée (conditionnée par des hypothèses largement admises telles que la conjecture P NP) au moyen de réductions . Dans le cas du problème métrique du voyageur de commerce, le résultat d'inapproximation le plus connu exclut les algorithmes avec un rapport d'approximation inférieur à 123/122 1,008196 à moins que P = NP, Karpinski, Lampis, Schmied. Couplé à la connaissance de l'existence de l'algorithme d'approximation 1.5 de Christofides, cela nous indique que le seuil d'approximation pour le voyageur de commerce métrique (s'il existe) se situe quelque part entre 123/122 et 1.5.

Alors que les résultats d'inapproximation ont été prouvés depuis les années 1970, de tels résultats ont été obtenus par des moyens ad hoc et aucune compréhension systématique n'était disponible à l'époque. Ce n'est que depuis le résultat de 1990 de Feige, Goldwasser, Lovász, Safra et Szegedy sur l'inapproximabilité de l'Ensemble Indépendant et le célèbre théorème PCP , que des outils modernes pour prouver les résultats d'inapproximabilité ont été découverts. Le théorème PCP, par exemple, montre que les algorithmes d'approximation de Johnson de 1974 pour Max SAT , ensemble couverture , ensemble indépendant et coloration atteignent tous le rapport d'approximation optimal, en supposant P NP.

Praticité

Tous les algorithmes d'approximation ne sont pas adaptés aux applications pratiques directes. Certains impliquent la résolution de programmation linéaire non triviale / relaxations semi - définies (qui peuvent elles-mêmes invoquer l' algorithme ellipsoïde ), des structures de données complexes ou des techniques algorithmiques sophistiquées, entraînant des problèmes de mise en œuvre difficiles ou des performances de temps d'exécution améliorées (par rapport aux algorithmes exacts) uniquement sur des entrées peu pratiques. . Mis à part les problèmes de mise en œuvre et de temps d'exécution, les garanties fournies par les algorithmes d'approximation peuvent elles-mêmes ne pas être suffisamment solides pour justifier leur considération en pratique. Malgré leur incapacité à être utilisés "prêts à l'emploi" dans des applications pratiques, les idées et les idées qui sous-tendent la conception de tels algorithmes peuvent souvent être incorporées d'autres manières dans des algorithmes pratiques. De cette façon, l'étude d'algorithmes, même très coûteux, n'est pas une poursuite complètement théorique car ils peuvent fournir des informations précieuses.

Dans d'autres cas, même si les premiers résultats sont d'un intérêt purement théorique, au fil du temps, avec une meilleure compréhension, les algorithmes peuvent être affinés pour devenir plus pratiques. Un tel exemple est le PTAS initial pour Euclidienne TSP par Sanjeev Arora (et indépendamment par Joseph Mitchell ) qui avait un temps d'exécution prohibitif de pour une approximation. Pourtant, en l'espace d'un an, ces idées ont été incorporées dans un algorithme de temps quasi-linéaire pour toute constante . ${\displaystyle n^{O(1/\epsilon )}}$${\style d'affichage 1+\epsilon }$${\displaystyle O(n\log n)}$${\displaystyle \epsilon >0}$

Garanties de performance

Pour certains algorithmes d'approximation, il est possible de prouver certaines propriétés concernant l'approximation du résultat optimal. Par exemple, un ρ algorithme -approximation A est défini comme un algorithme pour lequel il a été prouvé que la valeur / coût, f ( x ), de la solution approchée A ( x ) à une instance x ne sera pas plus (ou moins, en fonction de la situation) d'un facteur de les fois la valeur, OPT, d'une solution optimale.

${\displaystyle {\begin{cases}\mathrm {OPT} \leq f(x)\leq \rho \mathrm {OPT} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }}\rho <1.\end{cases}}}$

Le facteur ρ est appelé la garantie de performance relative . Un algorithme d'approximation a une garantie de performance absolue ou une erreur bornée c , s'il a été prouvé pour chaque instance x qui

${\displaystyle (\mathrm {OPT} -c)\leq f(x)\leq (\mathrm {OPT} +c).}$

De même, la garantie de performance , R ( x,y ), d'une solution y à une instance x est définie comme

${\displaystyle R(x,y)=\max \left({\frac {OPT}{f(y)}},{\frac {f(y)}{OPT}}\right),}$

où f ( y ) est la valeur/le coût de la solution y pour l'instance x . En clair, la garantie de performance est 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 a un rapport d'approximation de r ( n ). De même, un problème avec un algorithme d'approximation r ( n ) est dit r ( n ) - approché ou a un rapport d'approximation de r ( n ).

Pour les problèmes de minimisation, les deux garanties différentes fournissent le même résultat et que pour les problèmes de maximisation, une garantie de performance relative de est équivalente à une garantie de performance de . Dans la littérature, les deux définitions sont communes mais il est clair quelle définition est utilisée puisque, pour les problèmes de maximisation, comme ρ ≤ 1 tandis que r 1. ${\displaystyle r=\rho ^{-1}}$

La garantie de performance absolue d'un algorithme d'approximation A , où x fait référence à une instance d'un problème, et où est la garantie de performance de A sur x (c'est-à-dire ρ pour l'instance de problème x ) est : ${\displaystyle \mathrm {P} _{A}}$${\style d'affichage R_{A}(x)}$

${\displaystyle \mathrm {P} _{A}=\inf\{r\geq 1\mid R_{A}(x)\leq r,\forall x\}.}$

C'est-à-dire que c'est la plus grande borne du rapport d'approximation, r , que l'on voit sur toutes les instances possibles du problème. De même, le rapport de performance asymptotique est : ${\displaystyle \mathrm {P} _{A}}$ ${\displaystyle R_{A}^{\infty }}$

${\displaystyle R_{A}^{\infty }=\inf\{r\geq 1\mid \exists n\in \mathbb {Z} ^{+},R_{A}(x)\leq r,\ pour tout x,|x|\geq n\}.}$

C'est-à-dire qu'il est le même que le ratio de performance absolu , avec une borne inférieure n sur la taille des instances du problème. Ces deux types de ratios sont utilisés car il existe des algorithmes où la différence entre ces deux est significative.

Garanties de performance

	r -environ	ρ -approx	rel. Erreur	rel. Erreur	norme. rel. Erreur	abdos. Erreur
max : ${\style d'affichage f(x)\geq }$	${\displaystyle r^{-1}\mathrm {OPT} }$	${\displaystyle \rho \mathrm {OPT} }$	${\displaystyle (1-c)\mathrm {OPT} }$	${\displaystyle (1-c)\mathrm {OPT} }$	${\displaystyle (1-c)\mathrm {OPT} +c\mathrm {PIRE} }$	${\displaystyle \mathrm {OPT} -c}$
min : ${\style d'affichage f(x)\leq }$	${\displaystyle r\mathrm {OPT} }$	${\displaystyle \rho \mathrm {OPT} }$	${\displaystyle (1+c)\mathrm {OPT} }$	${\displaystyle (1-c)^{-1}\mathrm {OPT} }$	${\displaystyle (1-c)^{-1}\mathrm {OPT} +c\mathrm {PIRE} }$	${\displaystyle \mathrm {OPT} +c}$

termes Epsilon

Dans la littérature, un rapport d'approximation pour un problème de maximisation (minimisation) de c - (min : c + ϵ) signifie que l'algorithme a un rapport d'approximation de c ∓ ϵ pour ϵ arbitraire > 0 mais que le rapport n'a pas (ou ne peut pas être montré pour ϵ = 0. Un exemple de ceci est l'inapproximation optimale — l'inexistence d'approximation — le rapport de 7 / 8 + ϵ pour les instances MAX-3SAT satisfiables dues à Johan Håstad . Comme mentionné précédemment, lorsque c = 1, le problème est dit avoir 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 alors que l'optimum minimum des instances de taille n tend vers l'infini comme n . Dans ce cas, le rapport d'approximation est c ∓ k / OPT = c ∓ o(1) pour certaines constantes c et k . Étant donné ϵ arbitraire > 0, on peut choisir un N suffisamment grand tel que le terme k / OPT < ϵ pour tout n ≥ N . Pour chaque ϵ fixe, les instances de taille n < N peuvent être résolues par force brute, montrant ainsi un rapport d'approximation — existence d'algorithmes d'approximation avec une garantie — de c ∓ ϵ pour tout ϵ > 0.

Voir également

• L'analyse de dominance considère les garanties en termes de rang de la solution calculée.
• PTAS - un type d'algorithme d'approximation qui prend le rapport d'approximation comme paramètre
• APX est la classe de problèmes avec un algorithme d'approximation à facteur constant
• Réduction préservant l'approximation
• Algorithme exact

Citations

Les références

• Vazirani, Vijay V. (2003). Algorithmes d'approximation . Berlin : Springer. ISBN 978-3-540-65367-7.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest et Clifford Stein . Introduction aux algorithmes , deuxième édition. MIT Press et McGraw-Hill, 2001. ISBN  0-262-03293-7 . Chapitre 35 : Algorithmes d'approximation, pp. 1022-1056.
• Dorit S. Hochbaum , éd. Algorithmes d'approximation pour les problèmes NP-difficiles , PWS Publishing Company, 1997. ISBN  0-534-94968-1 . Chapitre 9 : Diverses notions d'approximations : bonnes, meilleures, meilleures et plus
• Williamson, David P. ; Shmoys, David B. (26 avril 2011), The Design of Approximation Algorithms , Cambridge University Press , ISBN 978-0521195270

Liens externes

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski et Gerhard Woeginger , Un recueil de problèmes d'optimisation NP .