Die Frage ist: Gibt es immer ein Polyzeit-Approximationsschema für NP-vollständige Probleme mit pseudo-polynomiellen Zeitalgorithmen (wie zum Beispiel Rucksack)?
Die kurze Antwort lautet NEIN. Petra Schuurman und Gerhard Woeginger haben darüber in ihrem Tutorial geschrieben . Siehe Beispiel 0.6.3 auf S.46 in ihrem Artikel, wenn es kein FPTAS gibt, während das Problem einen Pseudopolynomalgorithmus hat. Was ein Beispiel betrifft, wenn es kein PTAS gibt, während das Problem einen Pseudopolynomalgorithmus hat, schlage ich das Problem der binären Lackiererei vor (auch hier diskutiert , Definition finden Sie in der ersten Antwort).
Auch im Tutorial auf S. 5 gibt es ein gutes Bild über die Beziehungen zwischen Approximationsklassen und Pseudo-Polynomialzeit.
Es hängt davon ab, ob. Gerhard Woeginger hat einen Artikel über ein verwandtes Problem: Wenn eine dynamische Programmierformulierung eines Problems zu einem PTAS führt .
Sie sollten sich Abschn. 2.4. von Giorgio Ausiello, Pierluigi Crescenzi, Marco Protasi: Ungefähre Lösung von NP-Optimierungsproblemen. Theor. Comput. Sci. 150 (1): 1-55 (1995) .