Definición de PTAS vs. FPTAS

Por lo que leí en el 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 es la definición de PTAS :

Un esquema de aproximación de tiempo polinomial ( PTAS ) para el problema es un esquema de aproximación cuya complejidad de tiempo es polinómica en el tamaño de entrada.$X$

y definición de FPTAS

Un esquema de aproximación de tiempo completamente polinomial ( FPTAS ) para el problema es un esquema de aproximación cuya complejidad de tiempo es polinomial en el tamaño de entrada y también polinomial en 1 / .$X$$\epsilon$

Entonces el escritor dice:

Por lo tanto, para un PTAS sería aceptable tener una complejidad temporal proporcional a dondees el tamaño de entrada; aunque esta vez la complejidad es exponencial en . Un FPTAS no puede tener una complejidad de tiempo que crezca exponencialmente en pero una complejidad de tiempo proporcional a estaría bien. Con respecto a la aproximación del peor de los casos, un FPTAS es el resultado más fuerte posible que podemos obtener para un problema NP-difícil. | Yo | 1 / ϵ 1 / ϵ | Yo | 8 / ϵ $|I|^{1/\epsilon}$$|I|$$1/\epsilon$$1/\epsilon$$|I|^8/\epsilon^3$

Luego sugirió la siguiente figura para ilustrar las relaciones entre las clases de problemas:

Aquí están mis preguntas:

1. De la definición de PTAS y FPTAS , ¿cómo concluye el escritor que el FPTAS no puede tener una complejidad temporal que crezca exponencialmente en ? ¿Y qué diferencia hace si puede tener tal complejidad de tiempo?$1/\epsilon$

2. Una complejidad de tiempo como es aceptable para FPTAS pero no es para PTAS , entonces ¿por qué se considera que FPTAS es un subconjunto de PTAS ?$(n+1/\epsilon)^3$

3. ¿Qué quiere decir con: un FPTAS es el resultado más fuerte posible que podemos obtener para un problema NP-difícil.

4. En conjunto, me gustaría saber qué significan exactamente estos conceptos y cuáles son sus propiedades distintivas.

Gracias por adelantado.

Déjame responder tus preguntas en orden:

1. Por definición, un problema tiene un FPTAS si hay un algoritmo que en los casos de longitud da una : Aproximación y se ejecuta en polinomio tiempo en y , que es para alguna constante . Un tiempo de ejecución de no pertenece a para cualquier . Un algoritmo cuyo tiempo de ejecución es es mejor que un algoritmo cuyo tiempo de ejecución solo se garantiza que sea , ya que la dependencia de$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$Es mejor para el primer algoritmo. Además, para cualquier , podemos encontrar una aproximación en tiempo polinómico usando el primer algoritmo pero no usando el segundo (al menos no con la garantía dada).$E$$1+1/n^E$

2. Un problema en el que se puede encontrar una aproximación en el tiempo está definitivamente en PTAS, ya que para cada esto es (ejercicio) y por lo tanto polinomial en .$1+\epsilon$$(n+1/\epsilon)^3$$\epsilon$$O(n^3)$$n$

3. Lo que los autores quisieron decir aquí es que, dado que un problema de optimización NP-hard no se puede resolver exactamente en tiempo polinómico, lo mejor que podemos esperar es que sea -proximable en tiempo polinómico, y además con una buena dependencia de . Entre las clases de complejidad comunes, FPTAS ofrece la garantía más sólida de la dependencia de . Pero en la práctica a veces obtenemos una garantía aún mejor: el tiempo de ejecución es polinómico en y en . Por lo tanto, no es estrictamente cierto que FPTAS sea el resultado más sólido posible; es solo el resultado más fuerte posible entre las opciones PTAS, FPTAS, P. Si creamos una nueva clase LPTAS (correspondiente al polinomio de tiempo en$\epsilon$$\epsilon$$\epsilon$$n$$\log(1/\epsilon)$$n$y en ), eso sería una garantía más sólida.$\log(1/\epsilon)$

4. Dado un problema de optimización NP-hard, no se puede resolver exactamente en tiempo polinómico; lo mejor que se puede esperar es aproximarlo de manera eficiente. Algunos problemas son NP-difíciles de aproximar a algunos constantes . Para otros, es posible aproximar el problema arbitrariamente bien en tiempo polinómico, y estos problemas tienen un PTAS y, por lo tanto, pertenecen a la clase PTAS. Es posible que una aproximación tarde un tiempo proporcional a , por lo que solo podemos aplicar esto de manera eficiente para constante . Si el problema tiene un FPTAS (y pertenece a la clase FPTAS), entonces sabemos que la dependencia de es solo polinomial, por lo que podemos aproximarnos eficientemente a$C>1$$1+\epsilon$$e^{1/\epsilon}$$\epsilon$$\epsilon$$1+1/n^C$para cualquier .$C$

Deje que el tamaño de la instancia sea . La diferencia entre un PTAS y un FPTAS es que, en el anterior es una constante fija, por lo que puede tratarse como una constante. Es por eso que un tiempo de ejecución como sigue siendo polinomial en tamaño de instancia (también en tamaño de entrada ya que es una constante fija de todos modos). En un FPTAS, no es fijo. El esquema de aproximación debe ser polinomial en así como (es decir, como en ). Un tiempo de ejecución comoϵ n 1 / ϵ n ϵ ϵ 1 / ϵ n p o l y ( n , 1 / ϵ ) n 4 ( 1 / ϵ ) 3 + ( 1 / ϵ ) 8 n 1 / ϵ n 1 /$|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}$no es claramente polinomio en y . Por lo tanto, dicho esquema de aproximación es un PTAS pero no un FPTAS.$n$$1/\epsilon$