难解问题的固定参数近似算法研究进展
Advances in Fixed-parameter Tractable Approximation Algorithms for NP-hard Problems作者机构：湖南师范大学数学与计算机科学学院高性能计算与随机信息处理省部共建教育部重点实验室长沙410081 西南民族大学计算机科学与技术学院成都610041
出 版 物：《计算机科学》 (Computer Science)
年 卷 期：2016年第43卷第8期
页 面：7-12,54页
学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）]
基 金：国家自然科学基金项目(61572190 61379019) 四川省科技计划项目(2015JY002)资助
摘 要：固定参数近似算法采用参数计算方法寻求问题的近似解,是实际中处理难解问题的一种新的有效手段。根据难解问题的参数计算复杂性类别,综述了固定参数可解问题、参数计算复杂性未定问题和W[t]-难问题(t≥1)固定参数近似算法近年来的研究进展。对于上述每一类问题,分别归纳了当前的主要研究结果,分析了其中的主要算法设计技术并探讨了有待研究的相关问题。
维普期刊数据库
同方期刊数据库