形式陈述

对优化问题实例 $I$，设算法解值为 $A(I)$、最优值为 $\mathrm{OPT}(I)>0$。最小化问题的乘法近似比可写为

$${\rho }_A(n)=\underset{|I|=n}{sup}\frac{A(I)}{\mathrm{OPT}(I)}\ge 1;$$

最大化问题通常取 $sup\mathrm{OPT}(I)/A(I)$。若该比值至多常数 $\rho$，称为 $\rho$-近似。也可统一要求

$$max\{\frac{A}{\mathrm{OPT}},\frac{\mathrm{OPT}}{A}\}\le \rho ,$$

但零值、负值或符号变化的目标需改用加法误差或专门约定。

直觉

近似比衡量最坏实例上算法离最优解最多差一个乘法因子，而不是平均表现或某次实验误差。

例子与边界

一般图顶点覆盖中，取任一极大匹配的全部端点得到大小至多最优值两倍的覆盖，因此是 2-近似。对最大化问题，“得到最优值的 $90\mathrm{\%}$”也常称 $0.9$-approximation；本库采用比值至少为 $1$ 的对称记法时对应 $1/0.9$。必须在论文中明确约定，避免方向混淆。

推论与应用

近似比用于比较 NP-hard 优化问题的多项式时间算法，并组织 APX、PTAS 等近似复杂度层级。实际评测可同时报告经验 gap，但经验最优值不能替代对所有实例成立的证明保证。

参考资料

• Vijay V. Vazirani, Approximation Algorithms, Springer, 2001，Ch. 1, approximation algorithms and performance ratios。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Ch. 11, approximation algorithms and guarantees。