多项式时间近似方案

PTAS 让用户用精度参数换时间：它不是单个固定比算法，而是一族由 $\epsilon$ 控制的算法，每个固定 $\epsilon >0$ 都在输入规模上多项式，并达到 $1+\epsilon$（最小化）或相应最大化保证，因而可以任意接近最优。定义允许多项式次数依赖 $1/\epsilon$，所以 $n^{1/\epsilon }$ 仍是 PTAS；这正是它与 EPTAS、FPTAS 的主要分界，也意味着误差缩小时运行时间的次数或常数可能急剧增长。

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

对 Euclidean TSP，给定固定 $\epsilon$ 可得到 $(1+\epsilon )$-近似并在 $n$ 上多项式运行，是经典 PTAS 场景。若算法时间为 $n^{O(1/\epsilon )}$，对每个固定精度合格，却不是 FPTAS；若为 $2^{O(1/\epsilon )}{n}^3$，则属于 EPTAS 形式。

必须保证对所有实例达到给定近似比，不能由实验曲线代替。$\epsilon$ 是输入的一部分时，PTAS 定义不承诺对总编码长度多项式；FPTAS 才要求关于 $n$ 和 $1/\epsilon$ 都多项式。

PTAS 区分可获得任意精度近似的问题与只有固定常数保证的问题。APX公理库APXAPX · Approximable optimization problems在 NPO 框架中存在输入规模无关常数近似比的多项式时间组合优化问题类。只要求存在某个固定常数比，因此 $PTAS\subseteq APX$，反向一般不成立；gap reduction公理库Gap 问题与 gap reductionGap problem · Gap reduction · Gap-preserving reduction以带承诺的最优值阈值间隙和保持两端阈值的归约，把局部检验可靠性转化为不可近似性。则通过制造不可跨越的最优值间隙，排除过强的近似方案。

近似比公理库近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。提供精度语义，时间复杂度公理库时间复杂度Time complexity · Running time在固定计算模型与输入编码后，算法运行步骤数随输入规模增长的量级。约束每个固定 $\epsilon$ 的成本。它与FPT公理库参数化复杂度类 FPTFixed-parameter tractable · FPT可在 f(k)n^O(1) 时间内求解的参数化问题类。的形式相似但参数位置不同：EPTAS 把超多项式依赖隔离在精度参数上；具体问题是否拥有 PTAS，仍需算法构造或不可近似性证明，不能仅由它属于 APX 推出。

构造路线也决定运行时间对精度的依赖。缩放 FPTAS公理库通过缩放构造 FPTASFPTAS via scaling · value scaling FPTAS通过缩放并向下取整数值，把背包的伪多项式动态规划转为对输入规模与精度均多项式的方案。把伪多项式动态规划的数值范围压缩到 $\mathrm{poly}(n,1/\epsilon )$，而局部搜索近似公理库局部搜索近似local-search approximation · 局部搜索近似算法在可搜索邻域中反复严格改进，并由局部最优交换不等式推出全局近似保证。需同时证明可搜索的邻域、严格终止和局部最优质量。二者都可能产生方案，却不能只凭“精度可调”省略 FPTAS、EPTAS 与普通 PTAS 的时间分类。