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