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

Abstract:

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.

Key words: approximation algorithm；differential approximation；domination analysis；inapproximability