Polynomial time approximation schemes and parameterized complexity
Polynomial time approximation schemes and parameterized complexity
复制标题
多项式时间近似方案和参数化复杂度
DOI：
10.1016/j.dam.2006.04.040
复制
发表时间：
2007-01
影响因子：
1.1
通讯作者：
Ge Xia
中科院分区：
文献类型：
--
作者：
Iyad A. Kanj;Xiuzhen Huang;Jianer Chen;Ge Xia
本文研究了NP最优化问题的可逼近性与参数复杂性之间的关系。我们引入了多项式固定参数易处理性的概念，并证明了，在一个非常一般的约束下，NP优化问题有一个完全多项式时间近似计划，当且仅当该问题是多项式固定参数易处理的。通过对参数化复杂性理论中的W-族施加平面性约束，得到了一类NP最优化问题--平面W-族，并证明了这类问题都有有效的多项式时间近似格式（EPTAS）.平面W-层次结构似乎包含了大多数已知的EPTAS问题，并且与卡纳和Motwani在用多项式时间近似方法描述优化问题时所引入的类有很大的不同。
In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce a notion of polynomial fixed-parameter tractability and prove that, under a very general constraint, an NP optimization problem has a fully polynomial time approximation scheme if and only if the problem is polynomial fixed-parameter tractable. By enforcing a constraint of planarity on the W-hierarchy studied in parameterized complexity theory, we obtain a class of NP optimization problems, the planar W-hierarchy, and prove that all problems in this class have efficient polynomial time approximation schemes (EPTAS). The planar W-hierarchy seems to contain most of the known EPTAS problems, and is significantly different from the class introduced by Khanna and Motwani in their efforts in characterizing optimization problems with polynomial time approximation schemes.
登录
查看更多内容
DOI：
10.1016/0304-3975(80)90006-7
发表时间：
1979-05
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
G. Ausiello;A. Marchetti-Spaccamela;M. Protasi
通讯作者：
G. Ausiello;A. Marchetti-Spaccamela;M. Protasi
DOI：
10.1109/istcs.1993.253478
发表时间：
1993-06
期刊：
[1993] The 2nd Israel Symposium on Theory and Computing Systems
影响因子：
--
作者：
L. Cai;Jianer Chen
通讯作者：
L. Cai;Jianer Chen
DOI：
10.1145/504794.504798
发表时间：
2000-04
期刊：
J. ACM
影响因子：
--
作者：
Markus Frick;Martin Grohe
通讯作者：
Markus Frick;Martin Grohe
DOI：
10.1007/978-3-642-58412-1
发表时间：
1999
期刊：
--
影响因子：
--
作者：
G. Ausiello;A. Marchetti-Spaccamela;P. Crescenzi;G. Gambosi;M. Protasi;V. Kann
通讯作者：
G. Ausiello;A. Marchetti-Spaccamela;P. Crescenzi;G. Gambosi;M. Protasi;V. Kann
DOI：
10.1145/174644.174650
发表时间：
1983-11
期刊：
24th Annual Symposium on Foundations of Computer Science (sfcs 1983)
影响因子：
--
作者：
B. S. Baker
通讯作者：
B. S. Baker