近似算法之测度视角

• 作者: 李聪 王刚 骆志刚 黄旭慧
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 近似算法 微分近似 占优分析 不可近似性
• 年，卷（期）: 2012,（11）
• 所属期刊栏目: 高性能计算
• 页码范围: 83-90
• 页数: 8页
• 分类号: TP301
• 字数: 7737字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2012.11.015

摘要

标准近似、微分近似和占优分析是三种不同的近似算法度量方法.标准近似比度量近似解偏离最优解的相对误差.微分近似关注近似解解值在最优解值和最差解值所形成的区间内所处的位置.占优分析考虑近似解在所有可行解中的排名.本文综述相关概念和主要成果,以及各测度方法的优缺点.尤其关注以PCP定理及唯一博弈猜想为代表的不可近似性成果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王刚	国防科学技术大学计算机学院	16	158	6.0	12.0
2	骆志刚	国防科学技术大学计算机学院	21	149	7.0	12.0
3	黄旭慧	国防科学技术大学计算机学院	3	2	1.0	1.0
4	李聪	国防科学技术大学计算机学院	6	7	2.0	2.0