Standard approximation, differential approximation, and domination analysis are three different measures of approximation algorithms. The standard approximation ratio measures the relative error 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 feasible solutions. We survey concepts and main results in this domain, and also advantages and disadvantages 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.%标准近似、微分近似和占优分析是三种不同的近似算法度量方法.标准近似比度量近似解偏离最优解的相对误差.微分近似关注近似解解值在最优解值和最差解值所形成的区间内所处的位置.占优分析考虑近似解在所有可行解中的排名.本文综述相关概念和主要成果,以及各测度方法的优缺点.尤其关注以PCP定理及唯一博弈猜想为代表的不可近似性成果.
展开▼
