多项式时间近似算法

在计算机科学领域，多项式时间近似算法（PTAS）是一种用于优化问题（最常见的是NP-hard优化问题）的近似算法。

PTAS使用一个大于0的参数 ε，产生一个对于最小化问题能在 1 + ε 倍最优解内的解决方案（或最大化问题的 1 − ε 倍）。例如，对于欧几里得旅行商问题，现有的最好PTAS 将产生一个长度最多为 (1 + ε) L 的解，其中L是最短行程的长度。 [1] ε的大小越小，PTAS的近似性能比越靠近1，也即说明这个PTAS的计算结果越接近最优解。

对于一个固定大小的ε，PTAS 的运行时间必须是（对于问题大小）多项式的（例如对于一个原时间复杂度为O(2^n)的算法，它的PTAS时间复杂度可以为O(n^4*2^k)，其中k为参数），但对于不同的 ε，可以是不同的。时间复杂度为O(n^1/ε) 甚至O(n^exp(1/ε)) 的算法同样属于 PTAS。

参考

1. Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.