期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We derive results of the following flavor: If a combinatorial optimization problem can be formulated via a dynamic program of a certain structure and if the involved cost and transition functions satisfy certain arithmetical and structural conditions, then the optimization problem automatically possesses a fully polynomial time approximation scheme (FPTAS). Our characterizations provide a natural and uniform approach to fully polynomial time approximation schemes. We illustrate their strength and generality by deducing from them the existence of FPTASs for a multitude of scheduling problems. Many known approximability results follow as corollaries from our main result.
