多项式时间逼近算法

多项式时间逼近算法

我们可以找到一些 0-1 背包问题或子集和问题等 NP 完全问题的多项式时间解决方案。这些问题在现实世界中十分常见，因此必须有一些方法来处理这些问题。

多项式时间逼近算法（PTAS）是一种用于逼近优化问题的算法。对于 0-1 背包问题，有一个伪多项式解决方案，但当值很大时，该解决方案不可行。所以我们需要一种 PTAS 解决方案。

一些 NP 完全问题，如图着色、K 中心问题等，它们没有已知的多项式时间解决方案。PTAS 用于逼近算法。这些算法取参数 ε> 0，为了逼近，我们将最小化 (1 + ε) 并最大化 (1 - ε)。

示例

例如，如果我们选择一个最小化问题并取 ε = 0.5，那么使用 PTAS 找到的解接近 1.5。所以运行时间必须是关于 n 的多项式，但它可以是关于 ε 的指数。

萨穆尔·萨姆

更新于： 2020-06-17

837 次浏览

提升你的 职业

完成课程，获得认证

开始吧