Polynomial Time Approximation Schemes and Parameterized Complexity Academic Article

abstract

• In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce the notion of efficient 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 efficiently 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). Springer-Verlag 2004.

authors

• Chen, Jianer

published proceedings

• Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

• Chen, J., Huang, X., Kanj, I. A., & Xia, G.

complete list of authors

• Chen, J||Huang, X||Kanj, IA||Xia, G

publication date

• December 2004

published in

• Lecture Notes in Computer Science  Journal

start page

• 500

end page

• 512

volume

• 3153