Algorithme d'approximation

En informatique et en recherche opérationnelle , les algorithmes d'approximation sont des algorithmes efficaces qui trouvent des solutions approximatives aux problèmes d'optimisation (en particulier les 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 en conséquence de la conjecture largement répandue P ≠ NP . Selon 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 tente donc de comprendre dans quelle mesure il est possible d'approximer les solutions optimales à de tels problèmes en temps polynomial. Dans une écrasante majorité des cas, la garantie de ces algorithmes est une garantie 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 dans un facteur multiplicatif (prédéterminé) de la solution renvoyée. Cependant, il existe également de nombreux algorithmes d'approximation qui fournissent une garantie additive 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 la planification sur des machines parallèles non liées.

La conception et l'analyse des algorithmes d'approximation impliquent essentiellement 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 s’intéresse de plus en plus à la question de savoir jusqu’où nous pouvons 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’approximation 2 du problème de la forêt de Steiner par Agrawal et al. 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.

Un exemple simple d'algorithme d'approximation est celui du problème de couverture de vertex 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 vertex est de répéter le processus suivant : trouver une arête non couverte, ajouter ses deux extrémités à la couverture et supprimer toutes les arêtes incidentes à l'un ou l'autre des sommets du graphe. Comme toute couverture de vertex du graphe d'entrée doit utiliser un vertex distinct pour couvrir chaque arête qui a été considérée dans le processus (puisqu'elle forme un ) , la couverture de vertex produite est donc au plus deux fois plus grande que celle 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 approximabilité ; certains, comme le problème du sac à dos , peuvent être approximés dans un facteur multiplicatif , pour tout facteur fixé , 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 dans 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 en temps polynomial) 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 approximatives. $0ϵ>0$0}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/568095ad3924314374a5ab68fae17343661f2a71">

Il existe aujourd'hui plusieurs techniques établies pour concevoir des algorithmes d'approximation. Celles-ci incluent les suivantes.

1. Algorithme glouton
2. Recherche locale
3. Énumération et programmation dynamique (qui est également souvent utilisée pour les approximations paramétrées )
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 les plus courantes sont les suivantes.
   • Assouplissements de la programmation linéaire
   • Assouplissements de la programmation semi-définie
5. Méthodes prima-duales
6. Raccord double
7. Intégrer le problème dans une métrique, puis résoudre le problème sur la base de cette métrique. C'est ce qu'on appelle également l'intégration de métriques.
8. Échantillonnage aléatoire et utilisation du caractère aléatoire en général en conjonction avec les méthodes ci-dessus.

Bien que les algorithmes d'approximation fournissent toujours une garantie a priori du pire cas (qu'il soit additif ou multiplicatif), 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 autre algorithme d'approximation pour la couverture de vertex minimale qui résout une relaxation de programmation linéaire pour trouver une couverture de vertex 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 vertex optimale, cela donne un autre algorithme à 2 approximations. 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 vertex optimale).

Français Les algorithmes d'approximation en tant que domaine de recherche sont étroitement liés et informés par la théorie de l'inapproximabilité où la non-existence d'algorithmes efficaces avec certains rapports d'approximation est prouvée (conditionnée par des hypothèses largement répandues telles que la conjecture P ≠ NP) au moyen de réductions . Dans le cas du problème du voyageur de commerce métrique, le meilleur résultat d'inapproximabilité 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.

Bien que des résultats d'inapproximabilité aient été prouvés depuis les années 1970, ces 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 des 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 , set cover , independent set et coloring atteignent tous le rapport d'approximation optimal, en supposant que P ≠ NP.

Tous les algorithmes d'approximation ne sont pas adaptés aux applications pratiques directes. Certains impliquent la résolution de programmes linéaires non triviaux / relaxations semi-définies (qui peuvent elles-mêmes invoquer l' algorithme ellipsoïde ), de structures de données complexes ou de techniques algorithmiques sophistiquées, ce qui entraîne 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 prise en compte dans la pratique. Malgré leur incapacité à être utilisés « prêts à l'emploi » dans des applications pratiques, les idées et les connaissances 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 quête entièrement théorique car ils peuvent fournir des informations précieuses.

Dans d'autres cas, même si les résultats initiaux présentent un intérêt purement théorique, au fil du temps, grâce à une meilleure compréhension, les algorithmes peuvent être affinés pour devenir plus pratiques. Un exemple de ce type est le PTAS initial pour TSP euclidien de Sanjeev Arora (et indépendamment de 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 à temps quasi linéaire pour toute constante . $0ϵ>0$0}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/568095ad3924314374a5ab68fae17343661f2a71">

Étant donné un problème d’optimisation :

où est un problème d'approximation, l'ensemble des entrées et l'ensemble des solutions, on peut définir la fonction de coût :

et l'ensemble des solutions réalisables :

trouver la meilleure solution à un problème de maximisation ou de minimisation :

Étant donnée une solution réalisable , avec , nous voudrions une garantie de la qualité de la solution, qui est une performance à garantir (facteur d'approximation).

Plus précisément, ayant , l'algorithme a un facteur d'approximation (ou rapport d'approximation ) de si , nous avons :

• pour un problème de minimisation : , ce qui signifie à son tour que la solution prise par l'algorithme divisée par la solution optimale atteint un rapport de ;
• pour un problème de maximisation : , ce qui signifie à son tour que la solution optimale divisée par la solution prise par l'algorithme atteint un rapport de ;

L'approximation peut être prouvée comme étant stricte ( approximation stricte ) en démontrant qu'il existe des cas où l'algorithme fonctionne à la limite d'approximation, ce qui indique la rigueur de la limite. Dans ce cas, il suffit de construire une instance d'entrée conçue pour forcer l'algorithme à adopter un scénario du pire des cas.

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 d'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 ) d'une instance x ne sera pas supérieure (ou inférieure, selon la situation) à un facteur ρ fois la valeur, OPT, d'une solution optimale.

1;\\ ho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }} ho <1.\fin{cas}}}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d994a747b373509565531a3a90f73c8297824427">

Le facteur ρ est appelé garantie de performance relative . Un algorithme d'approximation a une garantie de performance absolue ou une erreur limitée c , s'il a été prouvé pour chaque 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 ) est la valeur/coût de la solution y pour l'instance x . De toute évidence, 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 renvoyer 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 taux d'approximation de r ( n ). De même, un problème avec un algorithme d'approximation r ( n ) est dit r ( n ) -approximable ou a un taux 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 . Dans la littérature, les deux définitions sont courantes mais il est clair laquelle est utilisée puisque, pour les problèmes de maximisation, comme ρ ≤ 1 tandis que r ≥ 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 :

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 :

C'est-à-dire qu'il s'agit du même 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 les deux est significative.

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 un ϵ arbitraire > 0 mais que le rapport n'a pas (ou ne peut pas) être montré pour ϵ = 0. Un exemple de ceci est le rapport optimal d'inapproximabilité — inexistence d'approximation — de 7 / 8 + ϵ pour les instances MAX-3SAT satisfaisables dû à 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 minimal des instances de taille n tend vers l'infini comme le fait n . Dans ce cas, le rapport d'approximation est c ∓ k / OPT = c ∓ o(1) pour certaines constantes c et k . Étant donné un ϵ arbitraire > 0, on peut choisir un N suffisamment grand pour 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, montrant ainsi un rapport d'approximation — existence d'algorithmes d'approximation avec une garantie — de c ∓ ϵ pour tout ϵ > 0.