多项式时间近似方案
多项式时间近似方案
我们可以找到一些关于NP完全问题的多项式时间解，例如0-1背包问题或子集和问题。这些问题在现实世界中非常流行，因此必须有一些方法来解决这些问题。
多项式时间近似方案(PTAS)是一种用于优化问题的近似算法。对于0-1背包问题，有一个伪多项式解决方案，但是当值较大时，该解决方案不可行。然后，我们需要一个PTAS解决方案。
一些NP完全问题，例如图着色，K中心问题等，它们没有已知的多项式时间解。PTAS 用于近似算法。这些算法的参数ε>0，并且要近似，我们将最小化（1+ε）和最大化（1-ε）。
示例
例如，如果我们选择一个最小化问题并采用ε=0.5，则使用PTAS的解决方案将近1.5。因此，运行时间必须是n的多项式，但可以是ε的指数。