近似算法之测度视角  

Approximation Algorithms:A Measure Perspective

作　　者：王刚[1] 骆志刚[1] 李聪[1] 黄旭慧[1] 

机构地区：[1]国防科学技术大学计算机学院,湖南长沙410073

出　　处：《计算机工程与科学》2012年第11期83-90,共8页Computer Engineering & Science

摘　　要：标准近似、微分近似和占优分析是三种不同的近似算法度量方法。标准近似比度量近似解偏离最优解的相对误差。微分近似关注近似解解值在最优解值和最差解值所形成的区间内所处的位置。占优分析考虑近似解在所有可行解中的排名。本文综述相关概念和主要成果,以及各测度方法的优缺点。尤其关注以PCP定理及唯一博弈猜想为代表的不可近似性成果。Standard approximation, differential approximation, and domination analysis are three dtt- ferent measures of approximation algorithms. The standard approximation ratio measures the relative er- ror between the optimal solution and the approximate solution. Differential approximation pays attention to the position of the approximate solution in the interval defined by the optimal solution value and the worst solution value. Domination analysis considers the rank of the approximate solution among all fea- sible solutions. We survey concepts and main results in this domain, and also advantages and disadvan- tages of the three measures. Special focus has been placed on inapproximability results such as those based on the PCP theorem and the Unique Games Conjecture.

关 键 词：近似算法 微分近似 占优分析 不可近似性 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]