Schéma d'approximation en temps entièrement polynomial
De Wikipedia, l'encyclopédie encyclopedia
Un schéma d'approximation en temps entièrement polynomial (FPTAS, pour « Fully Polynomial-Time Scheme ») est un algorithme permettant de trouver des solutions approximatives aux problèmes fonctionnels, en particulier aux problèmes d'optimisation. Un FPTAS prend en entrée une instance du problème et un paramètre ε > 0. Il renvoie en sortie une valeur d'au moins fois la valeur correcte, et au plus fois la valeur correcte.
Cet article est orphelin. Moins de trois articles lui sont liés ().
Vous pouvez aider en ajoutant des liens vers [[Schéma d'approximation en temps entièrement polynomial]]
dans les articles relatifs au sujet.
Dans le contexte des problèmes d'optimisation, ce qu'on appelle valeur correcte est la valeur de la solution optimale. Il est souvent sous-entendu qu'un FPTAS doit produire une solution valide (et pas seulement la valeur de la solution). Retourner une valeur et trouver une solution avec cette valeur sont équivalents si l'on suppose que le problème possède une autoréductibilité.
Pour un FPTAS, on demande que le temps d'exécution soit polynomial en la taille de l'instance et en 1/ε. Ainsi, un FPTAS est plus contraint qu'un schéma général d'approximation en temps polynomial (PTAS). Le temps d'exécution d'un PTAS général est polynomial dans la taille du problème pour chaque ε spécifique, mais peut être exponentiel en 1/ε[1].
Le terme FPTAS peut également être utilisé pour désigner la classe de problèmes qui ont un FPTAS. FPTAS est un sous-ensemble de PTAS qui, sauf si P=NP est un sous-ensemble strict[2].