s
19 708 Pages

Nell 'informatique et la recherche opérationnelle, un algorithme d'approximation est un algorithme utilisé pour trouver des solutions approchées à problèmes d'optimisation. Les algorithmes d'approximation sont souvent associés à des problèmes NP-dur; car il est peu probable qu'il y aurait des algorithmes exacts efficaces polynomiale qui permettent de résoudre les problèmes NP-difficiles, nous sommes satisfaits des solutions sous-optimales en temps polynomiale. A la différence de 'heuristique, Nous trouvons généralement assez bonnes solutions temps raisonnablement rapides, dans ce cas, nous voulons des solutions de qualité démontrable et runtimes avec des limites démontrables. Idéalement, l'approximation est optimale à un petit facteur constant (par exemple, moins de 5% de la solution). Les algorithmes d'approximation sont de plus en plus utilisés pour des problèmes où des algorithmes précis dans le temps polynomiale sont connus, mais trop cher à cause de la taille d'entrée.

Un exemple typique d'un algorithme d'approximation est celle pour le couvercle de sommet en graphiques: Trouvez un bord à découvert et ajouter « les deux » extrêmes à la couverture du sommet, jusqu'à ce qu'il n'y en a pas. Il est clair que la couverture qui en résulte est au plus deux fois plus grande que celle optimale. Ceci est un algorithme d'approximation de facteur constant avec un facteur de deux.

Les problèmes NP-difficiles varient considérablement dans leur approximabilité; certains, comme le problème d'emballage peuvent être estimés à l'intérieur de tout facteur supérieur à 1 (cette famille d'algorithmes d'approximation est souvent appelé schéma d'approximation en temps polynomial ou PTAS). D'autres sont impossibles à rapprocher au sein de tout facteur constant, ou même polynôme, à moins que P = NP, comme le problème de la clique maximum.

Les problèmes NP-difficiles peuvent souvent être exprimées en des programmes entiers (programmes entiers, IP) et résolu exactement temps exponentielle. De nombreux algorithmes d'approximation émergent de la relaxation de programmation linéaire de l'ensemble du programme.

Tous les algorithmes d'approximation conviennent pour toutes les applications pratiques. Ils utilisent souvent solveurs IP / LP / semidéfinie, structures de données complexes ou techniques algorithmiques sophistiquées qui conduisent à des problèmes de mise en œuvre difficile. En outre, certains algorithmes d'approximation ont peu de temps d'exécution pratique, même si elles sont en temps polynomial, par exemple, O (n2000). Cependant, l'étude des algorithmes très coûteux n'est pas une recherche tout à fait théorique, car il peut fournir des indications précieuses. Un exemple classique est le PTAS initial pour euclidienne TSP en raison de Sanjeev Arora qui avait un temps de fonctionnement prohibitif; Cependant, dans un an, Arora a perfectionné les idées en un algorithme en temps linéaire. Ces algorithmes sont également valables dans certaines applications où le temps et le coût de fonctionnement peuvent être justifiées, par exemple. biologie informatique, ingénierie financière, la planification des transports et gestion des stocks. Dans de tels scénarios, ils doivent rivaliser avec les formulations IP directes correspondantes.

Une autre limite d'approche est qu'il applique uniquement aux problèmes d'optimisation et non à problèmes de décision « Pure » comme satisfiability, mais il est souvent possible de concevoir des problèmes d'optimisation versionsi tels que le problème de la satisfiabilité maximale (SAT Max).

Le inapprossimabilità était un domaine fécond de la recherche dans le domaine de la théorie de la complexité des calculs à partir des résultats de 1990 Feige, Goldwasser, Lovasz, Safra et Szegedy dell 'ensemble indépendant. Après Arora et al. démontré le théorème de la PCP un an plus tard, il a été montré que les algorithmes d'approximation développé en 1974 par Max Johnson pour la SAT, la couverture des ensembles, l'ensemble indépendant et la coloration tous atteignent le rapport optimal d'approximation, en supposant P! = NP.

Garanties de performance

Pour certains algorithmes d'approximation, il est possible de prouver certaines propriétés sur le rapprochement du résultat optimal. Par exemple, un algorithme d'approximation ρ A est défini comme un algorithme pour lequel il est prouvé que la valeur / coût, fa(x), La solution approximative A(x) Par exemple x ne sera pas plus (ou moins, en fonction de la situation) grande d'un facteur ρ fois par rapport à la valeur, OPT, d'une solution optimale.

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

le facteur ρ il est appelé Garantie de performance relative. Un algorithme d'approximation a un Garantie absolue de la performance ou erreur limitée c, où il existe des preuves pour chaque instance x que

De même, la Garantie de performance, R(x, y), Une solution y par exemple x Elle est définie comme

R (x, y) =

fa(y) Est la valeur / coût de la solution y par exemple x. De toute évidence, la garantie de la performance est supérieure ou égale à 1 si et seulement si y Il est une solution optimale. Si un algorithme A garanties de retour des solutions avec une garantie de performance au maximum de r(n), Il est dit que A Il est un algorithme d'approximation r(n) Et il a un rapport de rapprochement de r(n). De même, un problème avec un algorithme d'approximation r(n) Est dit être r(n) -approximée ou qu'elle a un rapport approximatif de r(n).[1][2]

On peut noter que, pour les problèmes de minimisation, les deux garanties différentes donnent le même résultat et que, pour les problèmes de maximisation, une garantie de performance relative ρ équivaut à une garantie de bonne exécution . Dans la littérature, les deux définitions sont communes mais il est clair quelle est la définition utilisée depuis pour des problèmes de maximisation, puisque ρ ≤ 1 et r ≥ 1.

la Garantie absolue de la performance d'un algorithme d'approximation A, où x Il fait référence à l'instance d'un problème, et où Il est la garantie de la performance A sur x (Ie p pour l'instance du problème x) Est-ce:

Cela signifie que Il est la plus grande limite du rapport d'approximation, r, que vous voyez sur tous les cas possibles du problème. De même, la indice de performance asymptotique il est:

Cela signifie qu'il est le même rapport de rendement absolu, avec une limite inférieure n la taille des instances du problème. Ces deux types de rapports qu'ils utilisent, car il y a des algorithmes où la différence entre les deux est importante.

Garanties de performance
r-Env.[1][2] ρ-Env. Erreur rel.[2] Erreur rel.[1] Erreur rel. norme.[1][2] ass erreur.[1][2]
max:
min:

Les techniques de conception d'algorithmes

A l'heure actuelle, il existe plusieurs techniques standard qui sont utilisées pour concevoir un algorithme d'approximation. Ceux-ci sont les suivantes.

  1. avide algorithme
  2. Recherche locale
  3. et Enumeration programmation dynamique
  4. La résolution d'un relâchement de la programmation convexe pour obtenir une solution fractionnée. Ensuite convertir cette solution fractionnée dans un moyen possible d'une certaine solution d'arrondi appropriée. Les plus connus comprennent les suivants relaxations.
    1. relaxation de programmation linéaire
    2. Relaxation de semidéfinie
  5. Incorporer le problème dans une certaine mesure simple, puis le fixer sur la métrique. Ceci est également connu sous le nom incoporazione métrique.

Conditions epsilon

Dans la littérature, une valeur d'approximation pour un problème de maximisation (minimisation) de c - ε (min: c + ε), cela signifie que l'algorithme a un rapport d'approximation c ∓ ε pour un ε arbitraire> 0 mais que la relation est représentée (ou ne peut pas montrer) pour ε = 0. Un exemple de ceci est le rapport optimal de inapprossimabilità - dell'approssimabilità inexistencia - 8/7 + ε pour les instances satisfaisables de MAX-3SAT en raison de Johan Håstad.[3] Comme mentionné ci-dessus, lorsque c = 1, on dit que le problème a schéma d'approximation en temps polynomial.

Un terme ε peut apparaître quand un algorithme d'approximation introduit une erreur multiplicatif et erreur constante alors que la bonne taille minimale des cas n Il va à l'infini quand il fait n. Dans ce cas, le rapport d'approximation est ck / OPT = c ∓ ou (1) pour des constantes c et k. Étant donné un ε> 0 arbitraire, vous pouvez choisir un N suffisamment important pour que le terme k / OPT < ϵ per ogni n ≥ N. Pour chaque ε fixe, les instances de dimension n < N Ils peuvent être résolus au moyen du force brute, montrant ainsi un rapport d'approximation - existence d'algorithmes d'approximation avec une garantie - de c ∓ ε pour chaque ε> 0.

notes

  1. ^ à b c et G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela et M. Protasi, Complexité et approximation: problèmes d'optimisation combinatoire et leurs propriétés approximabilité, 1999.
  2. ^ à b c et Viggo Kann, Sur la approximabilité de NP-complets problèmes d'optimisation (PDF), 1992.
  3. ^ Johan Håstad, Quelques résultats inapproximabilité Optimal (ps), Dans Journal de l'ACM, 1999.

bibliographie

  • Vijay V. Vazirani, Des algorithmes d'approximation, Berlin, Springer, 2003 ISBN 3-540-65367-8.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, et Clifford Stein. Introduction aux algorithmes, 2e édition. MIT Press et McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapitre 35: s "Approximation Algorithm", pp. 1022-1056.
  • Dorit H. Hochbaum (ed.), Les algorithmes d'approximation pour les problèmes NP-difficiles, PWS Publishing Company, 1997. ISBN 0-534-94968-1. Chapitre 9: "diverses notions de Approximations: Bon, mieux, meilleur et plus".
  • David P. Williamson et David B. Shmoys, La conception d'algorithmes d'approximation, Cambridge University Press, le 26 Avril 2011, ISBN 978-0-521-19527-0.

liens externes

autorités de contrôle GND: (DE4500954-5