La pregunta es: ¿Existe siempre un esquema de aproximación de polivinilos para problemas con NP completo que tienen algoritmos de tiempo pseudopolinomiales (como la mochila, por ejemplo)?
La respuesta corta es no. Petra Schuurman y Gerhard Woeginger han escrito sobre esto en su tutorial . Vea el ejemplo 0.6.3 en la página 46 en su artículo cuando no hay FPTAS mientras el problema tiene un algoritmo pseudopolinomial. Lo que concierne a un ejemplo cuando no hay PTAS, mientras que el problema tiene un algoritmo pseudopolinomial, sugiero el problema del taller de pintura binaria (discutido también aquí , la definición se puede encontrar en la primera respuesta).
También hay una buena imagen en el tutorial en la página 5 sobre las relaciones entre las clases de aproximación y el tiempo pseudo-polinómico.
Depende. Gerhard Woeginger tiene un documento sobre un problema relacionado: cuando una formulación de programación dinámica de un problema conduce a un PTAS .
Deberías mirar a la Secta. 2.4. de Giorgio Ausiello, Pierluigi Crescenzi, Marco Protasi: solución aproximada de problemas de optimización de NP. Theor Comput Sci. 150 (1): 1-55 (1995) .