Voir la source de Schéma d'approximation en temps polynomial

En [[informatique]], un '''schéma d'approximation en temps polynomial''' (en anglais ''polynomial-time approximation scheme'', abrégé en '''PTAS''') est une famille d'[[algorithme d'approximation|algorithmes d'approximation]] pour des problèmes d'[[optimisation combinatoire]]. On dit aussi plus simplement '''schéma d'approximation polynomial'''. Le plus souvent, les problèmes d'optimisation combinatoire considérés sont [[NP-difficile]]s.

Plusieurs variantes des PTAS existent : des définitions plus restrictives comme les '''EPTAS''' et '''FPTAS''', ou d'autres qui reposent sur les [[algorithme probabiliste|algorithmes probabilistes]] comme les '''PRAS''' et '''FPRAS'''.

== Définition ==
Un PTAS est un algorithme qui prend en arguments une instance d'un problème d'optimisation et un paramètre <math>\varepsilon>0</math> et qui produit, en temps polynomial, une solution qui est optimale à un facteur <math>1+\varepsilon</math> près (ou <math>1-\varepsilon</math> pour un problème de maximisation).

Par exemple, pour le [[problème du voyageur de commerce]] euclidien, un PTAS prend en entrée la donnée de n coordonnées dans le plan (ou dans un [[espace euclidien]] de dimension d) dans un espace euclidien, ainsi que le paramètre <math>\varepsilon>0</math>. Le PTAS produit alors un tour dont la longueur est au plus  <math>(1+\varepsilon)\cdot L</math>, où <math>L</math> est la longueur du tour le plus court{{refm|"sa"|"sapg"}}.

On demande de plus que le temps d'exécution d'un PTAS soit polynomial en la taille <math>n</math> de l'instance pour chaque <math>\varepsilon</math> fixé,  mais il peut être différent pour des valeurs différentes de <math>\varepsilon</math>. Ainsi, un algorithme en temps <math>O(n^{1/\varepsilon})</math> ou même en <math>O(n^{\exp(1/\varepsilon)})</math> est considéré comme un PTAS.

==Variantes==

===Schémas déterministes===

Un problème qui se pose dans la pratique avec les algorithmes PTAS est que l'exposant du polynôme peut croître très rapidement quand  <math>\varepsilon</math> diminue, par exemple quand le temps est en 
<math>O(n^{1/\varepsilon})</math>. Une façon d'y répondre est de définir des schémas d'approximation  temps polynomial dits '''efficaces''' (en anglais '''EPTAS''' pour ''efficient polynomial-time approximation scheme''), pour lesquels on demande un temps d'exécution en <math>O(n^c)</math> pour une constante <math>c</math> indépendante de <math>\varepsilon</math>. On est ainsi assuré que l'accroissement la taille du problème  a le même effet relatif sur l'accroissement du temps de calcul, indépendamment du <math>\varepsilon</math> choisi ; la constante cachée dans le <math>O()</math> peut par contre dépendre arbitrairement de <math>\varepsilon</math>. Par exemple, la complexité d'un EPTAS peut par exemple être <math>n^{3}2^{\frac 1\varepsilon}</math>.

Un schéma encore plus restrictif, et utile en pratique, est le ''schéma d'approximation entièrement en temps polynomial'' (en anglais '''FPTAS''' pour ''fully polynomial-time approximation scheme''), dans lequel l'algorithme doit être en temps polynomial à la fois en la taille <math>n</math> du problème et en <math>1/\varepsilon</math>. Par exemple, la complexité d'un FPTAS peut par exemple être <math>n^{3}\left({\frac 1\varepsilon}\right)^2</math>. Tous les problèmes de la classe FPTAS sont à [[complexité paramétrée|complexité FPT]]. Un exemple de problème qui possède un FPTAS est le [[problème du sac à dos]]{{Référence nécessaire|date=28 janvier 2022}}.

Tout problème d'optimisation [[problème NP-complet|NP-complet]] avec une fonction d’objectif bornée polynomialement (''Strongly NP-complete'') ne peut avoir de solution FPTAS sauf si P=NP{{refm|"vvv"}}. La réciproque n'est toutefois pas vraie : si P n'est pas égal à NP, le problème du sac-à-dos à deux contraintes n'est plus fortement NP-difficile, mais n'a pas de schéma d'approximation FPTAS même si l’objectif optimal est polynomialement bornée{{refm|"kpp"}}.

Sauf si [[Problème P = NP|P = NP]], on a l'inclusion stricte FPTAS&nbsp;⊊&nbsp;PTAS&nbsp;⊊&nbsp;[[APX (complexité)|APX]]. Dans ce cas, un problème APX-difficile ne possède pas de schéma PTAS.

Une autre variante déterministe des PTAS est le ''schéma d'approximation en temps quasi polynomial'' (en anglais '''QPTAS''' pour ''quasi-polynomial-time approximation scheme''). Un tel schéma a une [[complexité en temps]] en <math>n^{\operatorname{polylog}(n)}</math> pour chaque <math>\varepsilon >0</math> fixé.

===Schémas randomisés===
Certains problèmes qui n'ont pas de PTAS peuvent admettre un  [[algorithme probabiliste]] avec des propriétés similaires, appelé un ''schéma d'approximation en temps polynomial randomisé'' (en anglais '''PRAS''' pour ''polynomial-time randomized approximation scheme''). Un PRAS est un algorithme qui prend en entrée une instance d'un problème d'optimisation et de comptage, et qui produit en temps polynomial une solution qui a une ''forte probabilité'' d'être optimale à un facteur <math>\varepsilon</math> près. Par convention, ''forte probabilité'' signifie une probabilité plus grande que 3/4, même si la plupart des classes de complexité est « robuste » (c'est-à-dire insensible) quant à des variations de la valeur exacte. Comme les PTAS, les PRAS doivent avoir un temps d'exécution polynomial en <math>n</math>, mais pas forcément en <math>\varepsilon</math> ; avec les mêmes restrictions que plus haut sur le temps d'exécution en fonction de <math>\varepsilon</math>, on définit un ''schéma d'approximation en temps polynomial randomisé efficace '' ou '''EPRAS''' similaire aux EPTAS, et un ''schéma d'approximation randomisé entièrement en temps polynomial'' ou '''FPRAS''' similaire aux FPTAS{{refm|"vvv"}}. Mark Jerrum et Alistair Sinclair ont été distingués par le prix Gödel en 1996 pour avoir prouvé que le calcul du nombre de couplages d'un graphe bipartite et celui du permanent d'une [[matrice à coefficients positifs]] pouvaient être réalisés par un algorithme de la classe FPRAS<ref>{{Article |langue=en |prénom1=Alistair |nom1=Sinclair |prénom2=Mark |nom2=Jerrum |titre=Approximate counting, uniform generation and rapidly mixing Markov chains |périodique=Information and Computation |volume=82 |numéro=1 |date=1989-07-01 |issn=0890-5401 |doi=10.1016/0890-5401(89)90067-9 |lire en ligne=http://www.sciencedirect.com/science/article/pii/0890540189900679 |consulté le=2020-10-16 |pages=93–133 }}</ref>.

== Notes et références ==
{{Références|références = 
<ref name="kpp">
{{ouvrage  | nom1 = Kellerer | prénom1 = Hans | nom2 = Pferschy | prénom2 = Ulrich | nom3 = Pisinger | prénom3 = David | titre = Knapsack Problems | année = 2010 (réimpression en softcover de la version de 2004)| éditeur = Springer|pages= 568|isbn=978-3-642-07311-3 }}.
</ref>
<ref name="vvv">
{{Approximation algorithms (Vazirani)}} p. 294–295.
</ref>
<ref name="sa">
{{Article|prénom=Sanjeev |nom=Arora | lien auteur = Sanjeev Arora
|titre=Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems
|périodique=Journal of the ACM|année=1998|volume=45|numéro=5|pages=753–782}}.
</ref>
<ref name="sapg">Sanjeev Arora a reçu le [[prix Gödel]] en 2010 pour le schéma d'approximation polynomiale du [[problème du voyageur de commerce]] dans le cas euclidien.
</ref>
}}
{{Traduction/Référence|en|Polynomial-Time Approximation Scheme|503007773 |type=note}}

== Articles connexes ==
*[[Algorithme d'approximation]]
*[[Théorie de la complexité des algorithmes]]
*[[Théorie des graphes]]

==Liens externes==
* {{Complexity Zoo|fin=A#apx|nom=APX}}
* {{Complexity Zoo|fin=P#ptas|nom=PTAS}}
* {{Complexity Zoo|fin=E#eptas|nom=EPTAS}}
* {{Complexity Zoo|fin=F#ftas|nom=FPTAS}}
* Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, [[Marek Karpinski]], et [[Gerhard Woeginger]], [http://www.nada.kth.se/~viggo/wwwcompendium/ ''A compendium of NP optimization problems'']. Une liste de problèmes d'optimisation de la classe NP qui possèdent des schémas.

{{Portail|informatique théorique}}

{{DEFAULTSORT:Polynomial-Time Approximation Scheme}}
[[Catégorie:Algorithmique]]
[[Catégorie:Théorie de la complexité des algorithmes]]