多项式时间近似方案

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

非负整数利润、整数重量编码的0–1 背包有 FPTAS，因此也有 PTAS。一般整数权度量 TSP 若存在 PTAS，则会推出 $P=NP$；排除这种方案须保留 $P\ne NP$ 假设。一个对每个固定 $\epsilon$ 都“最终很快”的算法仍必须给出统一、可计算的算法族；只证明存在非一致算法不能自动算作标准 PTAS。

对背包的最大化目标，取 $\epsilon =0.1$ 就要求输出可行选择，其利润至少为最优值的 $90\mathrm{\%}$；改变精度仍使用同一套可计算程序。若算法时间为 $n^{O(1/\epsilon )}$，对每个固定精度合格，但这个上界本身没有给出 FPTAS；若为 $2^{O(1/\epsilon )}{n}^3$，则属于 EPTAS 形式。

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

PTAS 区分可获得任意精度近似的问题与只有固定常数保证的问题。APX理路APXAPX · Constant-factor approximable optimization problems在 NPO 框架中存在输入规模无关常数近似比的多项式时间组合优化问题类。只要求存在某个固定常数比，因此 $PTAS\subseteq APX$，反向不是定义能推出的，标准 NPO 框架下在 $P\ne NP$ 假设下可由不可近似性结果排除；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^c 时间求解的参数化问题类；用顶点覆盖分支与核化解释固定指数及参数选择。的形式相似但参数位置不同：EPTAS 把超多项式依赖隔离在精度参数上；具体问题是否拥有 PTAS，仍需算法构造或不可近似性证明，不能仅由它属于 APX 推出。

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