On Fixed-Parameter Tractability and Approximability of NP Optimization Problems

by: Liming Cai, Jianer Chen

Journal of Computer and System Sciences, Vol. 54, No. 3. (June 1997), pp. 465-474.

View FullText article

DOI, ScienceDirect

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

AbnerCYH

Find related articles with these CiteULike tags

algorithms, complexity, optimization, parameterized

Abstract

Fixed-parameter tractability of NP optimization problems is studied by relating it to approximability of the problems. It is shown that an NP optimization problem is fixed-parameter tractable if it admits a fully polynomial-time approximation scheme, or if it belongs to the class MAX SNP or to the class MIN F+[Pi]1. This provides strong evidence that noW[1]-hard NP optimization problems belong to these optimization classes and includes a very large class of approximable optimization problems into the class of fixed-parameter tractable problems. Evidence is also demonstrated to support the current working hypothesis in the theory of fixed-parameter tractability.

@article{citeulike:1920965, abstract = {Fixed-parameter tractability of NP optimization problems is studied by relating it to approximability of the problems. It is shown that an NP optimization problem is fixed-parameter tractable if it admits a fully polynomial-time approximation scheme, or if it belongs to the class MAX SNP or to the class MIN F+[Pi]1. This provides strong evidence that noW[1]-hard NP optimization problems belong to these optimization classes and includes a very large class of approximable optimization problems into the class of fixed-parameter tractable problems. Evidence is also demonstrated to support the current working hypothesis in the theory of fixed-parameter tractability.}, author = {Cai, Liming and Chen, Jianer }, citeulike-article-id = {1920965}, doi = {10.1006/jcss.1997.1490}, journal = {Journal of Computer and System Sciences}, keywords = {algorithms, complexity, optimization, parameterized}, month = {June}, number = {3}, pages = {465--474}, posted-at = {2007-11-15 09:25:10}, priority = {2}, title = {On Fixed-Parameter Tractability and Approximability of NP Optimization Problems}, url = {http://dx.doi.org/10.1006/jcss.1997.1490}, volume = {54}, year = {1997} }

RIS record

TY - JOUR ID - citeulike:1920965 L3 - citeulike-article-id:1920965 TI - On Fixed-Parameter Tractability and Approximability of NP Optimization Problems JF - Journal of Computer and System Sciences VL - 54 IS - 3 SP - 465 EP - 474 N2 - Fixed-parameter tractability of NP optimization problems is studied by relating it to approximability of the problems. It is shown that an NP optimization problem is fixed-parameter tractable if it admits a fully polynomial-time approximation scheme, or if it belongs to the class MAX SNP or to the class MIN F+[Pi]1. This provides strong evidence that noW[1]-hard NP optimization problems belong to these optimization classes and includes a very large class of approximable optimization problems into the class of fixed-parameter tractable problems. Evidence is also demonstrated to support the current working hypothesis in the theory of fixed-parameter tractability. KW - algorithms KW - complexity KW - optimization KW - parameterized AU - Cai, Liming AU - Chen, Jianer PY - 1997/06// UR - http://dx.doi.org/10.1006/jcss.1997.1490 ER -

RIS BibTeX