Polynomial time approximation schemes and parameterized complexity. Chen, J., Huang, X., Kanj, I. A., & Xia, G. Discrete Applied Mathematics, 155(2):180--193, January, 2007. ![Polynomial time approximation schemes and parameterized complexity [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex 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.
@article{chen_polynomial_2007,
title = {Polynomial time approximation schemes and parameterized complexity},
volume = {155},
issn = {0166-218X},
url = {http://www.sciencedirect.com/science/article/B6TYW-4KB14J3-2/2/5ebf7e9ca18e8e6a0e6475741c9168b0},
doi = {10.1016/j.dam.2006.04.040},
abstract = {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.},
number = {2},
urldate = {2009-10-30TZ},
journal = {Discrete Applied Mathematics},
author = {Chen, Jianer and Huang, Xiuzhen and Kanj, Iyad A. and Xia, Ge},
month = jan,
year = {2007},
keywords = {Approximation algorithm, Parameterized complexity, Polynomial time approximation scheme, W-hierarchy},
pages = {180--193}
}
Downloads: 0
{"_id":"gjGsZAGfTJykRSqvJ","bibbaseid":"chen-huang-kanj-xia-polynomialtimeapproximationschemesandparameterizedcomplexity-2007","downloads":0,"creationDate":"2016-12-19T20:50:58.794Z","title":"Polynomial time approximation schemes and parameterized complexity","author_short":["Chen, J.","Huang, X.","Kanj, I. A.","Xia, G."],"year":2007,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","title":"Polynomial time approximation schemes and parameterized complexity","volume":"155","issn":"0166-218X","url":"http://www.sciencedirect.com/science/article/B6TYW-4KB14J3-2/2/5ebf7e9ca18e8e6a0e6475741c9168b0","doi":"10.1016/j.dam.2006.04.040","abstract":"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.","number":"2","urldate":"2009-10-30TZ","journal":"Discrete Applied Mathematics","author":[{"propositions":[],"lastnames":["Chen"],"firstnames":["Jianer"],"suffixes":[]},{"propositions":[],"lastnames":["Huang"],"firstnames":["Xiuzhen"],"suffixes":[]},{"propositions":[],"lastnames":["Kanj"],"firstnames":["Iyad","A."],"suffixes":[]},{"propositions":[],"lastnames":["Xia"],"firstnames":["Ge"],"suffixes":[]}],"month":"January","year":"2007","keywords":"Approximation algorithm, Parameterized complexity, Polynomial time approximation scheme, W-hierarchy","pages":"180--193","bibtex":"@article{chen_polynomial_2007,\n\ttitle = {Polynomial time approximation schemes and parameterized complexity},\n\tvolume = {155},\n\tissn = {0166-218X},\n\turl = {http://www.sciencedirect.com/science/article/B6TYW-4KB14J3-2/2/5ebf7e9ca18e8e6a0e6475741c9168b0},\n\tdoi = {10.1016/j.dam.2006.04.040},\n\tabstract = {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.},\n\tnumber = {2},\n\turldate = {2009-10-30TZ},\n\tjournal = {Discrete Applied Mathematics},\n\tauthor = {Chen, Jianer and Huang, Xiuzhen and Kanj, Iyad A. and Xia, Ge},\n\tmonth = jan,\n\tyear = {2007},\n\tkeywords = {Approximation algorithm, Parameterized complexity, Polynomial time approximation scheme, W-hierarchy},\n\tpages = {180--193}\n}\n\n","author_short":["Chen, J.","Huang, X.","Kanj, I. A.","Xia, G."],"key":"chen_polynomial_2007","id":"chen_polynomial_2007","bibbaseid":"chen-huang-kanj-xia-polynomialtimeapproximationschemesandparameterizedcomplexity-2007","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/B6TYW-4KB14J3-2/2/5ebf7e9ca18e8e6a0e6475741c9168b0"},"keyword":["Approximation algorithm","Parameterized complexity","Polynomial time approximation scheme","W-hierarchy"],"downloads":0,"html":""},"search_terms":["polynomial","time","approximation","schemes","parameterized","complexity","chen","huang","kanj","xia"],"keywords":["approximation algorithm","parameterized complexity","polynomial time approximation scheme","w-hierarchy"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}