期刊
INFORMS JOURNAL ON COMPUTING
卷 12, 期 1, 页码 57-74出版社
INFORMS
DOI: 10.1287/ijoc.12.1.57.11901
关键词
approximate algorithm; FPTAS; worst-case analysis; dynamic programming
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据