跳转到内容

多项式时间近似算法

维基百科,自由的百科全书

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

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

对于一个固定大小的ε,PTAS 的运行时间必须是(对于问题大小)多项式的(例如对于一个原时间复杂度为O(2^n)的算法,它的PTAS时间复杂度可以为O(n4*2k),其中k为参数),但对于不同的 ε,可以是不同的。时间复杂度为O(n1/ε) 甚至O(nexp(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.