When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
复制标题
DOI：
10.1287/ijoc.12.1.57.11901
复制
发表时间：
2000-01
期刊：
影响因子：
--
通讯作者：
G. Woeginger
中科院分区：
文献类型：
--
作者：
G. Woeginger
我们得出以下结果：如果组合优化问题可以通过特定结构的动态程序来表述，并且如果所涉及的成本和转移函数满足特定的算术和结构条件，则优化问题自动拥有完全多项式时间近似方案（FPTAS）。我们的表征为完全多项式时间近似方案提供了一种自然且统一的方法。我们通过推断 FPTAS 解决大量调度问题的存在来说明它们的优点和通用性。许多已知的近似性结果都是我们主要结果的推论。
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.