On fixed-parameter tractability and approximability of NP-hard optimization problems
On fixed-parameter tractability and approximability of NP-hard optimization problems
复制标题
DOI：
10.1109/istcs.1993.253478
复制
发表时间：
1993-06
期刊：
影响因子：
--
通讯作者：
L. Cai;Jianer Chen
中科院分区：
文献类型：
--
作者：
L. Cai;Jianer Chen
基于GC（s（n），Pi /sub k//sup L/）模型，研究了NP-难优化问题的固定参数易处理性和可逼近性.主要结果是：（1）一类NP-难优化问题，包括控制集和0 - 1整数规划问题，是固定参数易处理的当且仅当GC（s（n），Pi /sub 2//sup L/）包含在P中，其中s（n）满足Ω（log n）;（2）大多数可逼近的NP-难优化问题是固定参数易处理的.特别地，类MAX NP是固定参数易处理的;（3）一类优化问题不具有完全多项式时间近似方案，除非GC（s（n），Pi /sub k//sup L/）包含在P中，对于某些s（n）在Ω（log n）中并且对于某些k>l;以及（4）每个固定参数易处理的优化问题可以在多项式时间内近似为非平凡比率。
Fixed-parameter tractability and approximability of NP-hard optimization problems are studied based on a model GC(s(n), Pi /sub k//sup L/). The main results are (1) a class of NP-hard optimization problems, including dominating-set and zero-one integer-programing, are fixed-parameter tractable if and only if GC(s(n), Pi /sub 2//sup L/) contained in P for some s(n) in omega (log n); (2) most approximable NP-hard optimization problems are fixed-parameter tractable. In particular, the class MAX NP is fixed-parameter tractable; (3) a class of optimization problems do not have fully polynomial time approximation scheme unless GC(s(n), Pi /sub k//sup L/) contained in P for some s(n) in omega (log n) and for some k>l; and (4) every fixed-parameter tractable optimization problem can be approximated in polynomial time to a non-trivial ratio.>