Pertanyaannya adalah: Apakah skema perkiraan waktu-poli selalu ada untuk masalah NP-complete yang memiliki algoritma waktu pseudo-polinomial (seperti misalnya knapsack)?
Jawaban singkatnya adalah TIDAK. Petra Schuurman dan Gerhard Woeginger telah menulis tentang ini di tutorial mereka . Lihat Contoh 0.6.3 pada halaman 46 di makalah mereka ketika tidak ada FPTAS sementara masalahnya memiliki algoritma pseudopolinomial. Apa yang menjadi contoh ketika tidak ada PTAS sementara masalah memiliki algoritma pseudopolinomial Saya sarankan Binary Paint Shop Problem (dibahas juga di sini , definisi dapat ditemukan pada jawaban pertama).
Juga ada gambar yang bagus dalam tutorial pada hal.5 tentang hubungan antara kelas aproksimasi dan Waktu Pseudo-Polinomial.
Tergantung. Gerhard Woeginger memiliki makalah tentang masalah terkait: ketika formulasi pemrograman dinamis masalah mengarah ke PTAS .
Anda harus melihat Sekte. 2.4. dari Giorgio Ausiello, Pierluigi Crescenzi, Marco Protasi: Solusi Perkiraan Masalah Optimalisasi NP. Teor Komputasi. Sci. 150 (1): 1-55 (1995) .