On Fixed-Parameter Tractability and Approximability of NP Optimization Problems Academic Article

abstract

• Fixed-parameter tractability of NP optimization problems is studied by relating it to approximability of the problems. It is shown that an N P 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 + 1 . This provides strong evidence that no W[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. 1997 Academic Press.

authors

• Chen, Jianer

published proceedings

• Journal of Computer and System Sciences

altmetric score

• 3

author list (cited authors)

• Cai, L., & Chen, J.

citation count

• 54

complete list of authors

• Cai, Liming||Chen, Jianer

publication date

• June 1997

publisher

• Elsevier  Publisher

published in

• Journal of Computer and System Sciences  Journal

Digital Object Identifier (DOI)

• 10.1006/jcss.1997.1490

start page

• 465

end page

• 474

volume

• 54

issue

• 3

URL

• http%3A%2F%2Fdx.doi.org%2F10.1006%2Fjcss.1997.1490