Définition PTAS vs FPTAS

D'après ce que j'ai lu dans le preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D.

Voici la définition PTAS :

Un schéma d'approximation polynomiale du temps ( PTAS ) pour le problème est un schéma d'approximation dont la complexité temporelle est polynomiale dans la taille d'entrée.$X$

et définition FPTAS

Un schéma d'approximation temporelle entièrement polynomial ( FPTAS ) pour le problème est un schéma d'approximation dont la complexité temporelle est polynomiale dans la taille d'entrée et également polynomiale dans 1 / ϵ .$X$$\epsilon$

Ensuite, l'écrivain dit:

Par conséquent, pour un PTAS, il serait acceptable d'avoir une complexité temporelle proportionnelle à où | Je | est la taille d'entrée, bien que cette complexité temporelle soit exponentielle en 1 / ϵ . Un FPTAS ne peut pas avoir une complexité temporelle qui croît exponentiellement en 1 / ϵ mais une complexité temporelle proportionnelle à | Je | 8 / ϵ 3 serait bien. En ce qui concerne l'approximation du pire des cas, un FPTAS est le résultat le plus fort possible que nous pouvons déduire pour un problème NP-difficile.$|I|^{1/\epsilon}$$|I|$$1/\epsilon$$1/\epsilon$$|I|^8/\epsilon^3$

Il a ensuite suggéré la figure suivante pour illustrer les relations entre les classes de problèmes:

Voici mes questions:

1. $1/\epsilon$

2. $(n+1/\epsilon)^3$

3. Que veut-il dire par: un FPTAS est le résultat le plus fort possible que nous pouvons déduire pour un problème NP-difficile.

4. Dans l'ensemble, je voudrais savoir ce que signifient exactement ces concepts et quelles sont leurs propriétés distinctes.

Merci d'avance.

Permettez-moi de répondre à vos questions dans l'ordre:

1. $n$$1+\epsilon$$n$$1/\epsilon$$O((n/\epsilon)^C)$$C \geq 0$$2^{1/\epsilon}$$O((n/\epsilon)^C)$$C$
   $O((n/\epsilon)^C)$$O(n^C e^{D/\epsilon})$$\epsilon$$E$$1+1/n^E$

2. $1+\epsilon$$(n+1/\epsilon)^3$$\epsilon$$O(n^3)$$n$

3. $\epsilon$$\epsilon$$\epsilon$$n$$\log(1/\epsilon)$$n$$\log(1/\epsilon)$

4. $C>1$$1+\epsilon$$e^{1/\epsilon}$$\epsilon$$\epsilon$$1+1/n^C$$C$

$|I|=n$$\epsilon$$n^{1/\epsilon}$$n$$\epsilon$$\epsilon$$1/\epsilon$$n$$\mathrm{poly}(n,1/\epsilon)$$n^4 (1/\epsilon)^3 + (1/\epsilon)^8$$n^{1/\epsilon}$$n$$1/\epsilon$