Definição de PTAS vs. FPTAS

Pelo que li no 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.

Esta é a definição do PTAS :

Um esquema de aproximação de tempo polinomial ( PTAS ) para o problema é um esquema de aproximação cuja complexidade de tempo é polinomial no tamanho da entrada.$X$

e definição do FPTAS

Um esquema de aproximação de tempo totalmente polinomial ( FPTAS ) para o problema é um esquema de aproximação cuja complexidade de tempo é polinomial no tamanho da entrada e também polinomial em 1 / ϵ .$X$$\epsilon$

Então o escritor diz:

Portanto, para um PTAS, seria aceitável ter uma complexidade de tempo proporcional a onde | I | é o tamanho da entrada; embora essa complexidade de tempo seja exponencial em 1 / ϵ . Um FPTAS não pode ter uma complexidade de tempo que cresça exponencialmente em 1 / ϵ, mas uma complexidade de tempo proporcional a | I | 8 / ε 3 seria ótimo. Com relação à aproximação dos piores casos, um FPTAS é o resultado mais forte possível que podemos obter para um problema difícil de NP.$|I|^{1/\epsilon}$$|I|$$1/\epsilon$$1/\epsilon$$|I|^8/\epsilon^3$

Em seguida, ele sugeriu a figura a seguir para ilustrar os relacionamentos entre as classes de problemas:

Aqui estão as minhas perguntas:

1. $1/\epsilon$

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

3. O que ele quer dizer com: um FPTAS é o resultado mais forte possível que podemos obter para um problema difícil de NP.

4. No geral, eu gostaria de saber o que exatamente esses conceitos significam e quais são suas propriedades distintas.

Desde já, obrigado.

Deixe-me responder suas perguntas em ordem:

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$