Schéma d'approximation en temps polynomial

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique, un schéma d'approximation en temps polynomial (en anglais polynomial-time approximation scheme, abrégé en PTAS) est une famille d'algorithmes d'approximation pour des problèmes d'optimisation combinatoire (le plus souvent des problèmes d'optimisation NP-difficiles). On dit aussi plus simplement schéma d'approximation polynomial.

Plusieurs variantes existent, avec des définitions plus restrictives comme les EPTAS et FPTAS, ou utilisant de l’aléa comme les PRAS et FPRAS.

Définition[modifier | modifier le code]

Un PTAS est un algorithme qui prend en arguments une instance d'un problème d'optimisation et un paramètre et qui produit, en temps polynomial, une solution qui est optimale à un facteur près (ou pour un problème de maximisation). Par exemple, pour le problème du voyageur de commerce euclidien, un PTAS produit un tour dont la longueur est au plus , si est la longueur du tour le plus court[1],[2].

On demande de plus que le temps d'exécution d'un PTAS soit polynomial en la taille de l'instance pour chaque fixé, mais il peut être différent pour des valeurs différentes de . Ainsi, un algorithme en temps ou même en est considéré comme un PTAS.

Variantes[modifier | modifier le code]

Schémas déterministes[modifier | modifier le code]

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 diminue, par exemple quand le temps est en . 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 pour une constante indépendante de . 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 choisi ; bien entendu, la constante dans le peut toujours dépendre arbitrairement de . 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 du problème et en . Tous les problèmes de la classe FPTAS sont à complexité FPT. Un exemple de problème qui possède un FPTAS est le problème du sac à dos.

Tout problème d'optimisation NP-complet avec une fonction d’objectif bornée polynomialement (Strongly NP-complete) ne peut avoir de solution FPTAS sauf si P=NP[3]. 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 NP-difficile fort, mais n'a pas de schéma d'approximation FPTAS même si l’objectif optimal est polynomialement bornée[4].

Sauf si P = NP, on a l'inclusion stricte FPTAS ⊊ PTAS ⊊ 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 pour chaque fixé.

Schémas randomisés[modifier | modifier le code]

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 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 , mais pas forcément en  ; avec les mêmes restrictions que plus haut sur le temps d'exécution en fonction de , 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[3].

Notes et références[modifier | modifier le code]

  1. Sanjeev Arora, « Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems », Journal of the ACM, vol. 45, no 5,‎ , p. 753–782.
  2. 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.
  3. a et b (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7) p. 294–295.
  4. Hans Kellerer, Ulrich Pferschy et David Pisinger, Knapsack Problems, Springer, 2010 (réimpression en softcover de la version de 2004), 568 p. (ISBN 978-3-642-07311-3).

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Polynomial-Time Approximation Scheme » (voir la liste des auteurs).

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]