Garantie de performance

Garantie de performance

Algorithme d'approximation

Un algorithme d'approximation est une heuristique garantissant à la qualité de la solution fournie 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.

Donc, pour toute instance d'un problème de minimisation admettant un algorithme d'approximation avec facteur ρ > 1 (i.e. un algorithme ρ-approché), si z * est la valeur de la solution optimale et z la valeur de la solution donnée par l'algorithme d'approximation, on aura z \le \rho z^*. C'est le cas 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.

Pour toute instance d'un problème de maximisation admettant un algorithme d'approximation avec facteur 0 < ρ < 1 (on parle toujours d'algorithme ρ-approché), si z * est la valeur de la solution optimale et z la valeur de la solution donnée par l'algorithme d'approximation, on aura z \ge \rho z^*.

Parmi les problèmes NP-complets certains sont non-approximables, c'est-à-dire qu'ils n'admettent pas d'algorithme d'approximation. C'est le cas du Voyageur de commerce dans un graphe G = (V,E) avec des poids quelconques (positifs) puisque tout algorithme d'approximation pour ce problème dans le graphe complet KV où les arêtes de E ont une valeur nulle et les autres une valeur infiniment grande fournit une réponse au problème de décision NP-complet de statuer sur l'Hamiltonicité d'un graphe (en l'occurrence G est Hamitonien si et seulement si l'algorithme approché fournit une solution de valeur nulle).


Voir aussi

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Algorithme d%27approximation ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Garantie de performance de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • PERFORMANCE (art et esthétique) — «Performance»: ce vocable – loin de désigner un quelconque exploit sportif – relève de ce qu’il est convenu de considérer comme du franglais ; directement issu du verbe to perform , «interpréter», il est attesté au début des années 1970 dans le… …   Encyclopédie Universelle

  • Garantie — Eine Garantie (v. frz.: garantie, v. altfränk. weren gewährleisten, sicherstellen) ist eine Zusicherung eines bestimmten Handelns in einem bestimmten Fall. Inhaltsverzeichnis 1 Garantie in der Umgangssprache 2 Garantie im Zivilrecht 2.1… …   Deutsch Wikipedia

  • Garantie-Zertifikat — Zertifikate sind Wertpapiere und zählen zu den strukturierten Finanzprodukten. Sie werden von Banken emittiert und vorwiegend an Privatkunden verkauft; sie sind daher klassische Retail Produkte. Mit Zertifikaten wird auch dem Privatanleger… …   Deutsch Wikipedia

  • Fonds Négocié En Bourse — Un fonds négocié en bourse (aussi appelé fonds coté en bourse) est un véhicule de placement qui reproduit le comportement d’un indice boursier et qui est caractérisé par des frais d’administration minimes. Sommaire 1 Orthographe 2 Particularités… …   Wikipédia en Français

  • Fonds coté en bourse — Fonds négocié en bourse Un fonds négocié en bourse (aussi appelé fonds coté en bourse) est un véhicule de placement qui reproduit le comportement d’un indice boursier et qui est caractérisé par des frais d’administration minimes. Sommaire 1… …   Wikipédia en Français

  • Fonds cotés en bourse — Fonds négocié en bourse Un fonds négocié en bourse (aussi appelé fonds coté en bourse) est un véhicule de placement qui reproduit le comportement d’un indice boursier et qui est caractérisé par des frais d’administration minimes. Sommaire 1… …   Wikipédia en Français

  • Fonds negocie en bourse — Fonds négocié en bourse Un fonds négocié en bourse (aussi appelé fonds coté en bourse) est un véhicule de placement qui reproduit le comportement d’un indice boursier et qui est caractérisé par des frais d’administration minimes. Sommaire 1… …   Wikipédia en Français

  • Fonds négocié en bourse — Un fonds négocié en bourse (aussi appelé fonds coté en bourse) est un véhicule de placement qui reproduit le comportement d’un indice boursier et qui est caractérisé par des frais d’administration minimes. Sommaire 1 Particularités 2 Avantages… …   Wikipédia en Français

  • Fonds négociés en bourse — Fonds négocié en bourse Un fonds négocié en bourse (aussi appelé fonds coté en bourse) est un véhicule de placement qui reproduit le comportement d’un indice boursier et qui est caractérisé par des frais d’administration minimes. Sommaire 1… …   Wikipédia en Français

  • Optimisation combinatoire — L’optimisation combinatoire est une branche de l optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l algorithmique et la théorie de la complexité. On parle également d’optimisation discrète …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”