形式陈述

在标准的非负目标值约定下，对最小化问题，若存在统一算法族 $\{A_\varepsilon\}_{\varepsilon>0}$$\{A_{\epsilon }{\}}_{\epsilon >0}$，使每个固定 $\varepsilon>0$$\epsilon >0$ 下 $A_\varepsilon$$A_{\epsilon }$ 的运行时间关于输入规模 $n$$n$ 为多项式，且对所有满足 $\operatorname{OPT}(I)>0$$\mathrm{OPT}(I)>0$ 的实例有

$$ A_\varepsilon(I)\le(1+\varepsilon)\operatorname{OPT}(I), $$$$A_{\epsilon }(I)\le (1+\epsilon )\mathrm{OPT}(I),$$

则称为多项式时间近似方案（PTAS）；最大化问题相应要求 $A_\varepsilon(I)\ge(1-\varepsilon)\operatorname{OPT}(I)$$A_{\epsilon }(I)\ge (1-\epsilon )\mathrm{OPT}(I)$。目标可能为零、负数或变号时，必须另行规定乘法保证或改用加法误差。多项式次数可以依赖 $1/\varepsilon$$1/\epsilon$。若运行时间为 $f(1/\varepsilon)n^{O(1)}$$f(1/\epsilon )n^{O(1)}$，称 EPTAS；若对 $n$$n$ 与 $1/\varepsilon$$1/\epsilon$ 都为多项式，称 FPTAS。

直觉

用户用精度参数换时间：任意接近最优都能做到，但把误差缩小可能让多项式次数或常数急剧增长。

例子与边界

欧氏旅行商问题在固定维数有 PTAS；0–1 背包有 FPTAS。一般度量 TSP 若存在 PTAS 会产生与已知困难性冲突。一个对每个固定 $\varepsilon$$\epsilon$ 都“最终很快”的算法仍必须给出统一、可计算的算法族；只证明存在非一致算法不能自动算作标准 PTAS。

推论与应用

PTAS 区分可获得任意精度近似的问题与只有固定常数保证的问题。EPTAS 常与参数化复杂度联系，FPTAS 则提供更强的精度可扩展性；近似下界通常通过 gap-preserving reduction 排除某类方案。

参考资料

• Vijay V. Vazirani, Approximation Algorithms, Springer, 2001，Chs. 8–11, approximation schemes and representative PTAS/FPTAS results。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Ch. 11, approximation schemes。