Schéma d'approximation en temps entièrement polynomial

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 $1-\epsilon$ fois la valeur correcte, et au plus $1+\epsilon$ 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, x₁ ,..., x_n.
• Chaque vecteur d'entrée est composé de $a$ entiers non négatifs, où $a$ 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 $b$ entiers non négatifs, où $b$ 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 ₁ ,..., x _i. Les composants de l'APD sont :

• Un ensemble S ₀ 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 ₀ := 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 ₁ ,..., d _b ), appelé le vecteur degré du problème. Pour tout nombre réel r >1, on dit que deux vecteurs d'état s ₁, s ₂ sont (d,r)-proches si, pour chaque coordonnée j dans 1,..., b : $r^{-d_{j}}\cdot s_{1,j}\leq s_{2,j}\leq r^{d_{j}}\cdot s_{1,j}$ (en particulier, si d _j =0 pour certains j, alors $s_{1,j}=s_{2,j}$)

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

1. 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 tout deux vecteurs d'état s ₁, s ₂, on a : si s ₁ est ( d,r )-proche de s ₂, alors f ( s ₁, x ) est ( d,r )-proche de f ( s ₂ ,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.
2. 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 tout deux vecteurs d'état s ₁, s ₂, ce qui suit est vrai : si s ₁ est ( d,r )-proche de s ₂, alors : g ( s ₁ ) ≤ r ^G · g ( s ₂ ) (dans les problèmes de minimisation) ; g ( s ₁ ) ≥ r ^(-G) · g ( s ₂ ) (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.
3. 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 ₀ 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 ₁ (n,log(X)).
   • Si d _j =0, la cardinalité de V _j est au plus un polynôme P ₂ ( n ,log( X )).

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

• $\epsilon$ := le rapport d'approximation demandé.
• $r:=1+{\frac {\epsilon }{2Gn}}$, où G est la constante de la condition 2. Notons que ${\frac {1}{\ln {r}}}\leq 1+{\frac {2Gn}{\epsilon }}$.
• $L:=\left\lceil {\frac {P_{1}(n,\log(X))}{\ln(r)}}\right\rceil$, où P ₁ 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 $L\leq \left\lceil \left(1+{\frac {2Gn}{\epsilon }}\right)P_{1}(n,\log {X})\right\rceil$, il est donc polynomial en la taille de l'entrée et en $1/\epsilon$. Par ailleurs, $r^{L}=e^{\ln {r}}\cdot L\geq e^{P_{1}(n,\log {x})}$, donc par définition de P ₁, 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 : $I_{0}=[0];I_{1}=[1,r);I_{2}=[r,r^{2});\ldots ;I_{L}=[r^{L-1},r^{L}]$.
• 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 ₂ ( n ,log( X )) intervalles singletons - un intervalle pour chaque valeur possible de la coordonnée k (où P ₂ 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.
• $R:=(L+1+P_{2}(n,\log {X}))^{b}$.
  • 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 $1/\epsilon$.

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 ₀ := S ₀ = 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 $1/\epsilon$.

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 :

« Pour tout entier k dans 0,..., n, pour tout état s _s dans S _k, il existe un état s _t dans T _k qui est ( d, r ^k )-proche de s _s. »

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 ⁿ )-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, $r^{-Gn}\geq (1-\epsilon )$. Donc $g(t^{*})\geq (1-\epsilon )\cdot OPT$. 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.

1. 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)}. 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|| $\max C_{j}$ ou Qm|| $\max C_{j}$ ou Rm|| $\max C_{j}$.
   1. 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 ₁ - s ₂ ) ². Maintenant, la condition 2 est violée : les états ( s ₁, s ₁ ) et ( s ₁, s ₂ ) peuvent être ( d,r )-proches, mais g ( s ₁, s ₁ ) = 0 tandis que g ( s ₁, s ₂ ) > 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.
2. 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|| $\sum C_{j}^{3}$ - 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.
3. Somme des temps d'exécution pondérés sur tout nombre fixe de machines identiques ou uniformes - ce dernier étant noté Qm|| $\sum w_{j}C_{j}$.
4. Somme des temps d'exécution sur un nombre fixe quelconque de machines identiques ou uniformes, avec des temps de traitement dépendant du temps : Qm|time-dep| $\sum C_{j}$. Cela vaut même pour la somme pondérée des temps d'exécution.
5. Précocité-lenteur pondérée autour d'une date d'échéance commune sur tout nombre fixe de machines : m|| $\sum w_{j}|C_{j}|$.

Programme dynamique simple

Les programmes dynamiques simples ajoutent à la formulation ci-dessus les éléments suivants :

• Un ensemble H de fonctions de filtrage, de même cardinalité que F. Chaque fonction h _i dans H envoie une paire (état, entrée) sur une valeur booléenne. La valeur doit être "vrai" si et seulement si l'activation de la transition f _i sur ce couple conduirait à un état valide.
• Une relation de domination, qui est un ordre partiel sur les états (pas d'indifférences, toutes les paires ne sont pas comparables), et une relation de quasi-domination qui est un préordre total sur les états (indifférences autorisées, toutes les paires sont comparables).

L'APD d'origine est modifié comme suit :

• Soit S ₀ := l'ensemble des états initiaux.
• Pour k = 1 à n faire :
  • Soit S _k := { f_j ( s, x _k ) | f _j dans F, s dans S _{k -1}, h _j ( s, x _k ) = Vrai }, où h _j est la fonction de filtre correspondant à la fonction de transition f _j.
• Retourner min/max {g(s) | s dans S _n }.

Un problème est dit bienveillant s'il satisfait les conditions suivantes (qui prolongent les conditions 1, 2, 3 ci-dessus) :

1. 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 toute paire de vecteurs d'état s ₁, s ₂, ce qui suit est vrai :
   • si s ₁ est ( d,r )-proche de s ₂ , et s ₁ quasi-domine s ₂, alors soit (a) f ( s ₁, x ) est ( d,r )-proche de f ( s ₂, x ), et f ( s ₁, x ) quasi-domine f ( s ₂ ,x ), ou (b) f ( s ₁, x ) domine f ( s ₂ ,x ).
   • si s ₁ domine s ₂, alors f ( s ₁, x ) domine f ( s ₂ ,x ).
2. La proximité est préservée par la fonction valeur : il existe un entier G ≥ 0 (fonction de la fonction valeur g et du vecteur degré d ), tel que pour tout r >1, et pour toute paire de vecteurs d'état s ₁, s ₂, ce qui suit est vrai :
   • si s ₁ est ( d,r )-proche de s ₂, et s ₁ quasi-domine s ₂ , alors : g ( s ₁ ) ≤ r ^G · g ( s ₂ ) (dans les problèmes de minimisation) ; g ( s ₁ ) ≥ r ^(-G) · g ( s ₂ ) (dans les problèmes de maximisation).
   • si s ₁ domine s ₂, alors g ( s ₁ ) ≤ g ( s ₂ ) (dans les problèmes de minimisation) ; g ( s ₁ ) ≥ g ( s ₂ ) (dans les problèmes de maximisation).
3. Conditions techniques (en plus de ce qui précède):
   • La relation de quasi-dominance peut être décidée en temps polynomial.
4. Conditions sur les fonctions de filtrage : Pour tout r >1, pour toute fonction de filtrage h dans H, pour tout vecteur d'entrée x, et pour tout paire de vecteurs d'état s ₁, s ₂, ce qui suit est vrai :
   • si s ₁ est ( d,r )-proche de s ₂ , et s ₁ quasi-domine s ₂, alors h ( s ₁, x ) ≥ h ( s ₂, x ).
   • si s ₁ domine s ₂, alors h ( s ₁, x ) ≥ h ( s ₂, x ).

Pour chaque problème bienveillant, le programme dynamique peut être transformé en FPTAS de la même manière que celui ci-dessus, avec deux modifications (en gras) :

• Soit T ₀ := S ₀ = l'ensemble des états initiaux.
• Pour k = 1 à n faire :
  • On pose U _k := { F _j ( s, X _k ) | f _j dans F, s dans T _{k -1}, h _j ( s, x _k ) = Vrai }, où h _j est la fonction de filtre correspondant à la fonction de transition f _j.
  • 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, choisir un seul élément qui domine presque tous les autres éléments de U _k , et l'insérer dans T _k.
• Retourner min/max {g(s) | s dans T _n }.

Exemples

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

1. Le problème du sac à dos 0-1 est bienveillant. Ici, nous avons a =2 : chaque entrée est un 2-vecteur (poids, valeur). Il existe un APD avec b =2 : chaque état code (poids courant, valeur courante). Il existe deux fonctions de transition : f ₁ correspond à ajouter l'élément d'entrée suivant, et f ₂ correspond à ne pas l'ajouter. Les fonctions de filtrage correspondantes sont : h ₁ vérifie que le poids avec l'élément d'entrée suivant est au plus la capacité du sac à dos ; h ₂ renvoie toujours Vrai. La fonction valeur g ( s ) renvoie s ₂. L'ensemble d'états initial est {(0,0)}. Le vecteur degré est (1,1). La relation de dominance est triviale. La relation de quasi-domination ne compare que la coordonnée de poids : s quasi-domine t ssi s ₁ ≤ t ₁. La conséquence de ceci est que, si l'état t a un poids supérieur à l'état s, alors les fonctions de transition sont autorisées à ne pas préserver la proximité entre t et s (il est possible, par exemple, que s ait un successeur et que t n'ait pas de successeur correspondant). Un algorithme similaire a été présenté plus tôt par Ibarra et Kim. Le temps d'exécution de ce FPTAS peut être amélioré en $O(n\log {1/\epsilon }+1/\epsilon ^{4})$ opérations sur les nombres entiers. L'exposant a ensuite été amélioré à 2,5.
   1. Remarque : considérons le problème du sac à dos à 2 pondérations, où chaque élément a deux poids et une valeur, et le but est de maximiser la valeur de sorte que la somme des carrés des poids totaux soit au plus la capacité du sac à dos : $\left(\sum _{k\in K}w_{1,k}\right)^{2}+\left(\sum _{k\in K}w_{2,k}\right)^{2}\leq W$. Nous pourrions le résoudre en utilisant un APD similaire, où chaque état est (poids actuel 1, poids actuel 2, valeur). La relation de quasi-domination doit être modifiée comme suit : s quasi-domine t ssi ( s ₁ ² + s ₂ ² ) ≤ ( t ₁ ² + t ₂ ² ). Mais cela viole la condition 1 ci-dessus : la quasi-domination n'est pas préservée par les fonctions de transition [par exemple, l'état (2,2,..) quasi-domine (1,3,..) ; mais après avoir ajouté l'entrée (2,0,..) aux deux états, le résultat (4,2,..) ne domine pas quasi (3,3,.. )]. Le théorème ne peut donc pas être utilisé. En effet, ce problème n'a de FPTAS que si P=NP. Il en va de même pour le problème bidimensionnel du sac à dos. Il en va de même pour le problème de somme de sous-ensembles multiples : la relation de quasi-domination devrait être : s quasi-domine t ssi max( s _1, s ₂ ) ≤ max( t _1, t ₂ ), mais elle n'est pas préservée par les transitions, par le même exemple que ci-dessus.
2. Minimiser le nombre pondéré de travaux en retard ou maximiser le nombre pondéré de travaux en avance sur une seule machine ; noté 1|| $\sum w_{j}U_{j}$.
3. Planification par lots pour minimiser le nombre pondéré de travaux en retard : 1|batch| $\sum w_{j}U_{j}$.
4. Exemple de travaux en détérioration sur une seule machine : 1|détériorer| $\max C_{j}$.
5. Travail en retard total sur une seule machine : 1|| $\sum V_{j}$.
6. Travail en retard total pondéré sur une seule machine : 1|| $\sum w_{j}V_{j}$.

Non-exemples

Malgré la généralité du résultat ci-dessus, il existe des cas dans lesquels il ne peut pas être utilisé.

1. Dans le problème de retard total 1|| $\sum T_{j}$, la formulation de programmation dynamique de Lawler nécessite de mettre à jour tous les états de l'ancien espace d'états B fois, où B est de l'ordre de X (la taille d'entrée maximale). Il en est de même pour un ADP de lotissement économique Dans ces cas, le nombre de fonctions de transition dans F est B, qui est exponentiel en log( X ), donc la deuxième condition technique est violée. La technique de réduction d'état n'est pas utile, mais une autre technique - l'arrondi d'entrée - a été utilisée pour concevoir un FPTAS.
2. Dans le problème de minimisation de la variance 1|| $CTV$, la fonction objectif est $g(s)=s_{5}-(s_{4}-s_{3})^{2}/n$, qui viole la condition 2, donc le théorème ne peut pas être utilisé. Mais différentes techniques ont été utilisées pour concevoir un FPTAS.

Autres problèmes notables qui ont un FPTAS

• Le problème du sac à dos, ainsi que certaines de ses variantes :
  • 0-1 problème de sac à dos.
  • Problème de sac à dos illimité.
  • Problème de sac à dos multidimensionnel avec contraintes delta-modulaires.
  • Problème de sac à dos multi-objectif 0-1.
  • Problème de sac à dos paramétrique.
  • Problème de sac à dos quadratique symétrique.
• Count-subset-sum (# SubsetSum) - trouver le nombre de sous-ensembles distincts avec une somme d'au plus C.
• Chemin le plus court restreint : recherche d'un chemin de coût minimum entre deux nœuds d'un graphe, soumis à une contrainte de délai.
• Chemins les plus courts et objectifs non linéaires.
• Décompte recouvrements.
• Problème de recherche de sous-ensemble vectoriel où la dimension est fixée.

Bibliographie

• (en) Doerr, Eremeev, Neumann et Theile, « Evolutionary algorithms and dynamic programming », Theoretical Computer Science, vol. 412, n^o 43,‎ 7 octobre 2011, p. 6020–6035 (ISSN 0304-3975, DOI 10.1016/j.tcs.2011.07.024, lire en ligne)

Liens externes

• Zoo de la complexité, FPTAS