Un schéma d'approximation en temps entièrement polynomial (FPTAS, pour ) 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.

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/ε..

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..

Relation avec d'autres classes de complexité Tous les problèmes dans FPTAS sont traitables à paramètres fixes par rapport à la paramétrisation standard..

Tout problème d'optimisation fortement NP-difficile (autrement dit qui reste NP-difficile si on considère les nombres de l'instance écrit en unaire) avec une fonction objectif polynômialement bornée ne peut pas avoir de FPTAS à moins que P = NP. Cependant, la réciproque n'est pas vrai : par exemple, si P n'est pas égal à NP, le sac à dos avec deux contraintes n'est pas fortement NP-difficile, mais n'a pas de FPTAS même lorsque l'objectif optimal est polynômialement borné..

Transformation d'un programme dynamique en FPTAS Woeginger a présenté une méthode générale pour transformer une certaine classe de programmes dynamiques en FPTAS.

Entrée La méthode traite les problèmes d'optimisation dans lesquels l'entrée est définie comme suit :

L'entrée est constituée de n vecteurs, x1 ,..., xn. Chaque vecteur d'entrée est composé de entiers non négatifs, où peut dépendre de l'entrée. Toutes les composantes des vecteurs d'entrée sont codées en binaire. La taille de l'entrée est donc O(n +log X), où X est la somme de toutes les composantes de tous les vecteurs.

Programme dynamique extrêmement simple On suppose que le problème admet un algorithme de programmation dynamique (APD) utilisant des états. Chaque état est un vecteur composé de entiers non négatifs, où est indépendant de l'entrée. L'APD fonctionne en n étapes. A chaque étape i, il traite l'entrée x i, et construit un ensemble d'états S i. Chaque état code une solution partielle au problème, en utilisant les entrées x 1 ,..., x i. Les composants de l'APD sont :

Un ensemble S 0 d' états initiaux. Un ensemble F de fonctions de transition. Chaque fonction f dans F associe une paire (état, entrée) vers un nouvel état. Une fonction objectif g, associant un état à sa valeur.

L'algorithme de l'APD est :

Soit S 0 := l'ensemble des états initiaux. Pour k = 1 à n faire : Soit S k := { f( s, x k ) | f dans F, s dans S k −1 } Retourner min/max {g(s) | s dans S n }.

Le temps d'exécution de l'APD est linéaire en le nombre d'états possibles. En général, ce nombre peut être exponentiel dans la taille du problème d'entrée : il peut être en O( n V b ), où V est le plus grand entier pouvant apparaître dans un état. Si V est en O( X ), alors le temps d'exécution est en O( n X b ), qui n'est qu'un temps pseudo-polynomial, puisqu'il est exponentiel en la taille du problème qui est en O(log X ).

La façon de le rendre polynomial est de réduire l'espace d'états : au lieu de conserver tous les états possibles à chaque étape, ne conserver qu'un sous-ensemble des états ; supprimer les États "suffisamment proches" des autres États. Sous certaines conditions, cet ajustement peut être effectué de manière à ne pas trop modifier la valeur de l'objectif.

Pour formaliser cela, nous supposons que le problème à résoudre a un vecteur entier non négatif d = ( d 1 ,..., d b ), appelé le vecteur degré du problème. Pour tout nombre réel r >1, on dit que deux vecteurs d'état s 1, s 2 sont (d,r)-proches si, pour chaque coordonnée j dans 1,..., b : (en particulier, si d j =0 pour certains j, alors )

Un problème est dit extrêmement bienveillant s'il satisfait les trois conditions suivantes :

La proximité est préservée par les fonctions de transition : Pour tout r >1, pour toute fonction de transition f dans F, pour tout vecteur d'entrée x, et pour tous deux vecteurs d'état s 1, s 2, on a : si s 1 est ( d,r )-proche de s 2, alors f ( s 1, x ) est ( d,r )-proche de f ( s 2 ,x ). La condition suivante est une condition suffisante. Pour toute fonction f ( s, x ) dans F, et pour toute coordonnée j dans 1,..., b, notons f j (s,x) la j -ième coordonnée de f. Ce f j peut être vu comme une fonction entière en b + a variables. Supposons que chacun de ces f j soit un polynôme à coefficients non négatifs. Convertissez-le en un polynôme d'une seule variable z, en substituant s =(z d1 ,...,z db ) et x =(1,...,1). Si le degré du polynôme résultant en z est au plus d j, alors la condition 1 est satisfaite. La proximité est préservée par la fonction valeur : il existe un entier G ≥ 0 (qui est fonction de la fonction valeur g et du vecteur degré d ), tel que pour tout r >1, et pour tous deux vecteurs d'état s 1, s 2, ce qui suit est vrai : si s 1 est ( d,r )-proche de s 2, alors : g ( s 1 ) ≤ r G · g ( s 2 ) (dans les problèmes de minimisation) ; g ( s 1 ) ≥ r (-G) · g ( s 2 ) (dans les problèmes de maximisation). Une condition suffisante pour cela est que la fonction g soit une fonction polynomiale (de b variables) à coefficients non négatifs. Conditions techniques : Toutes les fonctions de transition f dans F et la fonction de valeur g peuvent être évaluées en temps polynomial. Le nombre | F | des fonctions de transition est polynômial en n et log( X ). L'ensemble S 0 des états initiaux peut être calculé en temps polynomial en n et log( X ). Soit V j l'ensemble de toutes les valeurs pouvant apparaître en coordonnée j dans un état. Alors, le ln de chaque valeur de V j est au plus un polynôme P 1 (n,log(X)). Si d j =0, la cardinalité de V j est au plus un polynôme P 2 ( n ,log( X )).

Pour chaque problème extrêmement bienveillant, le programme dynamique peut être converti en FPTAS. Définissons :

:= le rapport d'approximation demandé. , où G est la constante de la condition 2. Notons que . , où P 1 est le polynôme de la condition 3 (une borne supérieure sur le ln de chaque valeur pouvant apparaître dans un vecteur d'état). Notons que , il est donc polynomial en la taille de l'entrée et en . Par ailleurs, , donc par définition de P 1, tout entier pouvant apparaître dans un vecteur d'état est dans l'intervalle [0, r L ]. Une partition de la plage [0, r L ] en L +1 r -intervalles : . Une partition de l'espace d'états en r-boîtes : chaque coordonnée k de degré d k ≥ 1 est partitionnée en L +1 intervalles ci-dessus ; chaque coordonnée avec d k = 0 est partitionnée en P 2 ( n ,log( X )) intervalles singletons - un intervalle pour chaque valeur possible de la coordonnée k (où P 2 est le polynôme de la condition 3 ci-dessus). Notons que chaque état possible est contenu dans exactement une r -boîte ; si deux états sont dans la même r -boîte, alors ils sont ( d, r )-proches. . Notons que le nombre de r -boîtes est au plus R. Puisque b est une constante fixée, ce R est polynomial en la taille de l'entrée et en .

Le FPTAS fonctionne de manière similaire à l'APD, mais à chaque étape, il réduit l'ensemble d'états en un ensemble plus petit T k, qui contient exactement un état dans chaque r -box. L'algorithme du FPTAS est :

Soit T 0 := S 0 = l'ensemble des états initiaux. Pour k = 1 à n faire : On pose U k := { F ( s, X k ) | f dans F, s dans T k −1 } On pose T k := une copie tronquée de U k : pour chaque r -boîte qui contient un ou plusieurs états de U k, garder exactement un état dans T k. Retourner min/max {g(s) | s dans T n }.

Le temps d'exécution du FPTAS est polynomial dans le nombre total d'états possibles dans chaque T i, qui est au plus le nombre total de r -boîtes, qui est au plus R, qui est polynomial en n, log( X ), et .

Notons que, pour chaque état s u dans U k, son sous-ensemble T k contient au moins un état s t qui est (d,r)-proche de s u. De même, chaque U k est un sous-ensemble des S k dans l'APD d'origine (non réduit). Le lemme principal pour prouver la correction du FPTAS est :

La preuve est par récurrence sur k. Pour k =0 on a T k = S k ; tout état est ( d ,1)-proche de lui-même. Supposons que le lemme soit vrai pour k -1. Pour tout état s s dans S k, soit s s- un de ses prédécesseurs dans S k-1, de sorte que f ( s s −, x )= s s. Par hypothèse de récurrence, il existe un état s t- dans T k-1, c'est-à-dire ( d, r k-1 )-proche de s s −. Comme la proximité est préservée par les transitions (Condition 1 ci-dessus), f ( s t −, x ) est ( d, r k-1 )-proche de f ( s s −, x )= s s. Ce f ( s t −, x ) est dans U k. Après la réduction, il existe un état s t dans T k qui est ( d, r )-proche de f(s t- ,x). Ce s t est ( d, r k )-proche de s s.

Considérons maintenant l'état s * dans S n, qui correspond à la solution optimale (c'est-à-dire g ( s* )=OPT). D'après le lemme ci-dessus, il existe un état t * dans T n, qui est ( d, r n )-proche de s *. Comme la proximité est préservée par la fonction valeur, on a g (t*) ≥ r (-Gn) · g ( s* ) pour un problème de maximisation. Par définition de r, . Donc . Un argument similaire fonctionne pour un problème de minimisation.

Exemples Voici quelques exemples de problèmes extrêmement bienveillants, qui ont un FPTAS par le théorème ci-dessus..

Le partitionnement de nombres multiple (de manière équivalente, l'ordonnancement de machines identiques ) dans le but de minimiser la plus grande somme est extrêmement bienveillant. Ici, nous avons a = 1 (les entrées sont des nombres entiers) et b = le nombre de cases (qui est considéré comme fixe). Chaque état est un vecteur de b entiers représentant les sommes des b cases. Il y a b fonctions : chaque fonction j représente l'insertion de l'entrée suivante dans la case j. La fonction g ( s ) sélectionne le plus grand élément de s. S 0 = {(0,...,0)}. Les conditions d'extrême-bienveillance sont satisfaites avec le vecteur-degré d =(1,...,1) et G =1. Le résultat s'étend à l'ordonnancement des machines uniformes et l'ordonnancement des machines non liées quand le nombre de machines est fixe (ceci est nécessaire car R - le nombre de r -boîtes - est exponentiel en b ). Noté Pm|| ou Qm|| ou Rm|| . Remarque : considérons le cas particulier b =2, où le but est de minimiser le carré de la différence entre les deux sommes partielles. Le même APD peut être utilisé, mais cette fois avec la fonction valeur g ( s ) = ( s 1 - s 2 ) 2. Maintenant, la condition 2 est violée : les états ( s 1, s 1 ) et ( s 1, s 2 ) peuvent être ( d,r )-proches, mais g ( s 1, s 1 ) = 0 tandis que g ( s 1, s 2 ) > 0, donc le théorème ci-dessus ne peut pas être appliqué. En effet, le problème n'a pas de FPTAS à moins que P = NP, puisqu'un FPTAS pourrait être utilisé pour décider en temps poly si la valeur optimale est 0. Somme du temps d'exécution d'un travail au cube sur un nombre fixe de machines identiques ou uniformes - ce dernier étant noté Qm|| - est extrêmement-bienveillant avec a =1, b =3, d=(1,1,3). Il peut être étendu à n'importe quelle puissance fixe du temps de réalisation. Somme des temps d'exécution pondérés sur tout nombre fixe de machines identiques ou uniformes - ce dernier étant noté Qm|| .