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.

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 \varepsilon>0 et qui produit, en temps polynomial, une solution qui est optimale à un facteur 1+\varepsilon près (ou 1-\varepsilon 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 (1+\varepsilon)\cdot L, si L 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 n de l'instance pour chaque \varepsilon fixé, mais il peut être différent pour des valeurs différentes de \varepsilon. Ainsi, un algorithme en temps O(n^{1/\varepsilon}) ou même en O(n^{\exp(1/\varepsilon)}) 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 \varepsilon diminue, par exemple quand le temps est en O(n^{1/\varepsilon}). 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 O(n^c) pour une constante c indépendante de \varepsilon. 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 \varepsilon choisi ; bien entendu, la constante dans le O() peut toujours dépendre arbitrairement de \varepsilon. 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 n du problème et en 1/\varepsilon. 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 n^{\operatorname{polylog}(n)} pour chaque \varepsilon >0 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 \varepsilon 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 n, mais pas forcément en \varepsilon ; avec les mêmes restrictions que plus haut sur le temps d'exécution en fonction de \varepsilon, 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,‎ 1998, 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]