| 难解问题的固定参数近似算法研究进展 |
| |
| 引用本文： | 刘运龙,崔梦天. 难解问题的固定参数近似算法研究进展[J]. 计算机科学, 2016, 43(8): 7-12, 54 |
| |
| 作者姓名： | 刘运龙 崔梦天 |
| |
| 作者单位： | 湖南师范大学数学与计算机科学学院高性能计算与随机信息处理省部共建教育部重点实验室 长沙410081,西南民族大学计算机科学与技术学院 成都610041 |
| |
| 基金项目： | 本文受国家自然科学基金项目(61572190,61379019),四川省科技计划项目(2015JY002)资助 |
| |
| 摘 要： | 固定参数近似算法采用参数计算方法寻求问题的近似解,是实际中处理难解问题的一种新的有效手段。根据难解问题的参数计算复杂性类别,综述了固定参数可解问题、参数计算复杂性未定问题和W[t]-难问题(t≥1)固定参数近似算法近年来的研究进展。对于上述每一类问题,分别归纳了当前的主要研究结果,分析了其中的主要算法设计技术并探讨了有待研究的相关问题。
|
| 关 键 词： | 固定参数近似算法 W[t]-难 分支限界技术 |
| 收稿时间： | 2016-01-16 |
| 修稿时间： | 2016-05-11 |
Advances in Fixed-parameter Tractable Approximation Algorithms for NP-hard Problems |
| |
| LIU Yun-long and CUI Meng-tian. Advances in Fixed-parameter Tractable Approximation Algorithms for NP-hard Problems[J]. Computer Science, 2016, 43(8): 7-12, 54 |
| |
| Authors: | LIU Yun-long and CUI Meng-tian |
| |
| Affiliation: | Key Laboratory of High Performance Computing and Stochastic Information Processing Ministry of Education of China, College of Mathematics and Computer Science,Hunan Normal University,Changsha 410081,China and School of Computer Science and Technology,Southwest University for Nationalities,Chengdu 610041,China |
| |
| Abstract: | |
| |
| Keywords: | Fixed-parameter tractable approximation algorithm W[t]-hard Branching and searching |
|
|
点击此处可从《计算机科学》下载全文 |
|
