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 ${\displaystyle 1-\epsilon }$ fois la valeur correcte, et au plus ${\displaystyle 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/ε^[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^[2].

Relation avec d'autres classes de complexité

Tous les problèmes dans FPTAS sont traitables à paramètres fixes par rapport à la paramétrisation standard^[3].

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^[4] 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é^[5].

Transformation d'un programme dynamique en FPTAS

Woeginger^[6] 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 ${\displaystyle a}$ entiers non négatifs, où ${\displaystyle 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 ${\displaystyle b}$ entiers non négatifs, où ${\displaystyle 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 : ${\displaystyle 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 ${\displaystyle 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 :

• ${\displaystyle \epsilon }$ := le rapport d'approximation demandé.
• ${\displaystyle r:=1+{\frac {\epsilon }{2Gn}}}$, où G est la constante de la condition 2. Notons que ${\displaystyle {\frac {1}{\ln {r}}}\leq 1+{\frac {2Gn}{\epsilon }}}$.
• ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 1/\epsilon }$. Par ailleurs, ${\displaystyle 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 : ${\displaystyle 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.
• ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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^[7](Lem.3.3) :

« 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, ${\displaystyle r^{-Gn}\geq (1-\epsilon )}$. Donc ${\displaystyle 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^[6].

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|| ${\displaystyle \max C_{j}}$ ou Qm|| ${\displaystyle \max C_{j}}$ ou Rm|| ${\displaystyle \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|| ${\displaystyle \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|| ${\displaystyle \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| ${\displaystyle \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|| ${\displaystyle \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^[6].

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^[8]. Le temps d'exécution de ce FPTAS peut être amélioré en ${\displaystyle O(n\log {1/\epsilon }+1/\epsilon ^{4})}$ opérations sur les nombres entiers^[9]. L'exposant a ensuite été amélioré à 2,5^[10].
   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 : ${\displaystyle \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|| ${\displaystyle \sum w_{j}U_{j}}$.
3. Planification par lots pour minimiser le nombre pondéré de travaux en retard : 1|batch| ${\displaystyle \sum w_{j}U_{j}}$.
4. Exemple de travaux en détérioration sur une seule machine : 1|détériorer| ${\displaystyle \max C_{j}}$.
5. Travail en retard total sur une seule machine : 1|| ${\displaystyle \sum V_{j}}$.
6. Travail en retard total pondéré sur une seule machine : 1|| ${\displaystyle \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|| ${\displaystyle \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^[11] 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^[12],[13].
2. Dans le problème de minimisation de la variance 1|| ${\displaystyle CTV}$, la fonction objectif est ${\displaystyle 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^[14],[15].

Autres problèmes notables qui ont un FPTAS

• Le problème du sac à dos^[16],[17], ainsi que certaines de ses variantes :
  • 0-1 problème de sac à dos^[18].
  • Problème de sac à dos illimité^[19].
  • Problème de sac à dos multidimensionnel avec contraintes delta-modulaires^[20].
  • Problème de sac à dos multi-objectif 0-1^[21].
  • Problème de sac à dos paramétrique^[22].
  • Problème de sac à dos quadratique symétrique^[23].
• Count-subset-sum (# SubsetSum) - trouver le nombre de sous-ensembles distincts avec une somme d'au plus C^[24].
• 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^[25].
• Chemins les plus courts et objectifs non linéaires^[26].
• Décompte recouvrements.
• Problème de recherche de sous-ensemble vectoriel où la dimension est fixée^[27].

Notes et références

1. (de) G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, et M. Protasi, Complexity and Approximation: Combinatorial optimization problems and their approximability properties, Springer-Verlag, 1999.
2. (en) Ernst W. Mayr, Hans Jürgen Prömel et Angelika Steger, Lectures on Proof Verification and Approximation Algorithms, Springer Science & Business Media, 25 février 1998 (ISBN 978-3-540-64201-5, lire en ligne).
3. (en) Cai et Chen, « On Fixed-Parameter Tractability and Approximability of NP Optimization Problems », Journal of Computer and System Sciences, vol. 54, n^o 3,‎ juin 1997, p. 465–474 (DOI 10.1006/jcss.1997.1490, lire en ligne).
4. (en) Vijay V. Vazirani, Approximation Algorithms, Berlin, Springer, 2003, 294–295 p. (ISBN 3-540-65367-8).
5. (en) H. Kellerer and U. Pferschy and D. Pisinger, Knapsack Problems, Springer, 2004.
6. (en) Woeginger, « When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)? », INFORMS Journal on Computing, vol. 12, n^o 1,‎ 1^er février 2000, p. 57–74 (ISSN 1091-9856, DOI 10.1287/ijoc.12.1.57.11901, lire en ligne).
7. Woeginger, « When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)? », INFORMS Journal on Computing, vol. 12, n^o 1,‎ 1^er février 2000, p. 57–74 (ISSN 1091-9856, DOI 10.1287/ijoc.12.1.57.11901, lire en ligne)
8. (en) Ibarra et Kim, « Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems », Journal of the ACM, vol. 22, n^o 4,‎ 1^er octobre 1975, p. 463–468 (ISSN 0004-5411, DOI 10.1145/321906.321909, S2CID 14619586, lire en ligne).
9. Lawler, « Fast Approximation Algorithms for Knapsack Problems », Mathematics of Operations Research, vol. 4, n^o 4,‎ 1^er novembre 1979, p. 339–356 (ISSN 0364-765X, DOI 10.1287/moor.4.4.339, S2CID 7655435, lire en ligne).
10. (en) Rhee, Donguk, Faster fully polynomial approximation schemes for Knapsack problems (Thesis thesis), Massachusetts Institute of Technology, 2015. hdl:1721.1/98564.
11. (en) Florian, Lenstra et Rinnooy Kan, « Deterministic Production Planning: Algorithms and Complexity », Management Science, vol. 26, n^o 7,‎ 1^er juillet 1980, p. 669–679 (ISSN 0025-1909, DOI 10.1287/mnsc.26.7.669, lire en ligne)
12. (en) Lawler, « A fully polynomial approximation scheme for the total tardiness problem », Operations Research Letters, vol. 1, n^o 6,‎ 1^er décembre 1982, p. 207–208 (ISSN 0167-6377, DOI 10.1016/0167-6377(82)90022-0, lire en ligne).
13. (en) van Hoesel et Wagelmans, « Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems », Mathematics of operation research,‎ 1^er janvier 1997 (lire en ligne).
14. (en) Cai, « Minimization of agreeably weighted variance in single machine systems », European Journal of Operational Research, vol. 85, n^o 3,‎ 21 septembre 1995, p. 576–592 (ISSN 0377-2217, DOI 10.1016/0377-2217(93)E0367-7, lire en ligne).
15. (en) Woeginger, « An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine », INFORMS Journal on Computing, vol. 11, n^o 2,‎ 1^er mai 1999, p. 211–216 (ISSN 1091-9856, DOI 10.1287/ijoc.11.2.211, lire en ligne).
16. (en) Vijay Vazirani, Approximation algorithms, Berlin, Springer, 2001, 69–70 (ISBN 3540653678, OCLC 47097680, lire en ligne ).
17. (en) Kellerer et Pferschy, « Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem », Journal of Combinatorial Optimization, vol. 8, n^o 1,‎ 1^er mars 2004, p. 5–11 (ISSN 1573-2886, DOI 10.1023/B:JOCO.0000021934.29833.6b, S2CID 36474745, lire en ligne).
18. (en) Ce Jin, An Improved FPTAS for 0-1 Knapsack, vol. 132, coll. « Leibniz International Proceedings in Informatics (LIPIcs) », 2019, 76:1–76:14 (ISBN 9783959771092, DOI 10.4230/LIPIcs.ICALP.2019.76, arXiv 1904.09562, S2CID 128317990).
19. (en) Jansen et Kraft, « A faster FPTAS for the Unbounded Knapsack Problem », European Journal of Combinatorics, combinatorial Algorithms, Dedicated to the Memory of Mirka Miller, vol. 68,‎ 1^er février 2018, p. 148–174 (ISSN 0195-6698, DOI 10.1016/j.ejc.2017.07.016, arXiv 1504.04650, S2CID 9557898, lire en ligne).
20. (en) D. V. Gribanov, Mathematical Optimization Theory and Operations Research, vol. 12755, coll. « Lecture Notes in Computer Science », 10 mai 2021, 79–95 p. (ISBN 978-3-030-77875-0, DOI 10.1007/978-3-030-77876-7_6, arXiv 2103.07257, S2CID 232222954), « An FPTAS for the $$\var Delta $$-Modular Multidimensional Knapsack Problem »
21. (en) Bazgan, Hugot et Vanderpooten, « Implementing an efficient fptas for the 0–1 multi-objective knapsack problem », European Journal of Operational Research, vol. 198, n^o 1,‎ 1^er octobre 2009, p. 47–56 (ISSN 0377-2217, DOI 10.1016/j.ejor.2008.07.047, lire en ligne).
22. (en) Holzhauser et Krumke, « An FPTAS for the parametric knapsack problem », Information Processing Letters, vol. 126,‎ 1^er octobre 2017, p. 43–47 (ISSN 0020-0190, DOI 10.1016/j.ipl.2017.06.006, arXiv 1701.07822, S2CID 1013794, lire en ligne).
23. (en) Xu, « A strongly polynomial FPTAS for the symmetric quadratic knapsack problem », European Journal of Operational Research, vol. 218, n^o 2,‎ 16 avril 2012, p. 377–381 (ISSN 0377-2217, DOI 10.1016/j.ejor.2011.10.049, lire en ligne).
24. (en) Gopalan, Klivans, Meka et Štefankovic, « An FPTAS for #Knapsack and Related Counting Problems », 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science,‎ 1^er octobre 2011, p. 817–826 (ISBN 978-0-7695-4571-4, DOI 10.1109/FOCS.2011.32, S2CID 5691574, lire en ligne).
25. (en) Ergun, Sinha et Zhang, « An improved FPTAS for Restricted Shortest Path », Information Processing Letters, vol. 83, n^o 5,‎ 15 septembre 2002, p. 287–291 (ISSN 0020-0190, DOI 10.1016/S0020-0190(02)00205-3, lire en ligne).
26. (en) Tsaggouris et Zaroliagis, « Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications », Theory of Computing Systems, vol. 45, n^o 1,‎ 1^er juin 2009, p. 162–186 (ISSN 1433-0490, DOI 10.1007/s00224-007-9096-4, S2CID 13010023, lire en ligne).
27. (en) Kel’manov et Romanchenko, « An FPTAS for a vector subset search problem », Journal of Applied and Industrial Mathematics, vol. 8, n^o 3,‎ 1^er juillet 2014, p. 329–336 (ISSN 1990-4797, DOI 10.1134/S1990478914030041, S2CID 96437935, lire en ligne).

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

• Portail des mathématiques