A pergunta é: sempre existe um esquema de aproximação de politempo para problemas completos de NP que possuem algoritmos de tempo pseudo-polinomial (como mochila, por exemplo)?
A resposta curta é não. Petra Schuurman e Gerhard Woeginger escreveram sobre isso em seu tutorial . Veja o Exemplo 0.6.3 na p.46 em seu artigo quando não houver FPTAS enquanto o problema tiver um algoritmo pseudopolinomial. O que diz respeito a um exemplo quando não há PTAS enquanto o problema tem algoritmo pseudopolinomial? Sugiro Problema na Loja de Tinta Binária (discutido também aqui , a definição pode ser encontrada na primeira resposta).
Também há uma boa imagem no tutorial na p.5 sobre relações entre classes de aproximação e tempo pseudo-polinomial.
Depende. Gerhard Woeginger tem um artigo sobre um problema relacionado: quando uma formulação dinâmica de programação de um problema leva a um PTAS .
Você deveria olhar para a Seita. 2.4 de Giorgio Ausiello, Pierluigi Crescenzi, Marco Protasi: solução aproximada de problemas de otimização de NP. Theor. Comput. Sci. 150 (1): 1-55 (1995) .