%A LIU Yun-long and CUI Meng-tian %T Advances in Fixed-parameter Tractable Approximation Algorithms for NP-hard Problems %0 Journal Article %D 2016 %J Computer Science %R 10.11896/j.issn.1002-137X.2016.08.002 %P 7-12 %V 43 %N 8 %U {https://www.jsjkx.com/CN/abstract/article_15844.shtml} %8 2018-12-01 %X Fixed-parameter tractable approximation algorithm produces the approximation solution by using the approach of parameterized computation,which becomes one of the practical approaches to deal with NP-hard problems.In this paper,we investigated the fixed-parameter tractable approximation algorithms for various NP-hard problems according to their parameterized computational complexity.More specifically,we gave a survey on the fixed-parameter tractable approximation algorithms for the fixed-parameter tractable problems,the problems with unknown parameteri-zed computational complexity,and the W[t]-hard problems (t≥1) respectively.For each kind of problems,we summarized typical examples with their results obtained in recent years,analyzed the main techniques employed in the algorithms and discussed some issues to be further studied.