是一个完全多项式时间近似方案一个多项式时间近似方案
Is a fully polynomial-time approximation scheme a polynomial-time approximation scheme
我想知道一个近似方案是否是一个完全多项式时间近似方案 - 它是否也是一个多项式时间近似方案？
例如，一个运行时间为 O(n2(1/ε)3）的近似方案——我们知道这是一个完全多项式时间近似方案。
也是多项式时间逼近方案吗？谢谢！
这里有两个相关的问题（判断对错）：
- 对于任何固定的 ε>0，在 O(n 2/ε) 中运行的近似方案是
完全多项式时间近似方案。
- 对于任意固定ε>0，运行时间复杂度为O(n2(1/ε)3）的近似方案为
多项式时间近似方案。
感谢您提出有趣的问题。我做了一些研究，并在 PTAS（多项式时间近似方案）和完全 PTAS 上提出了这个 very nice academic lecture。
如讲座所述：
The running time of the algorithm should be polynomial in n; its
dependency on ε can be exponential however. So the running time can be
O((2 ^ (1/ε)) * n^2 ) for example, or O(n ^ (1/ε)), or O((n ^ 2)/ε), etc. If the
dependency on the parameter 1/ε is also polynomial then we speak of a
fully polynomial-time approximation scheme (FPTAS). In this lecture we
give an example of an FPTAS.
由于 PTAS 中 ε 的需求是指数相关的，那么 cleary FPTAS 是 PTAS 的一个子案例，因为 1/ε 是多项式相关的 ( O(FPTAS) < O(PTAS ))
底线 - FPTAS 是 PTAS。
我想知道一个近似方案是否是一个完全多项式时间近似方案 - 它是否也是一个多项式时间近似方案？
例如，一个运行时间为 O(n2(1/ε)3）的近似方案——我们知道这是一个完全多项式时间近似方案。
也是多项式时间逼近方案吗？谢谢！
这里有两个相关的问题（判断对错）：
- 对于任何固定的 ε>0，在 O(n 2/ε) 中运行的近似方案是 完全多项式时间近似方案。
- 对于任意固定ε>0，运行时间复杂度为O(n2(1/ε)3）的近似方案为 多项式时间近似方案。
感谢您提出有趣的问题。我做了一些研究，并在 PTAS（多项式时间近似方案）和完全 PTAS 上提出了这个 very nice academic lecture。
如讲座所述：
The running time of the algorithm should be polynomial in n; its dependency on ε can be exponential however. So the running time can be O((2 ^ (1/ε)) * n^2 ) for example, or O(n ^ (1/ε)), or O((n ^ 2)/ε), etc. If the dependency on the parameter 1/ε is also polynomial then we speak of a fully polynomial-time approximation scheme (FPTAS). In this lecture we give an example of an FPTAS.
由于 PTAS 中 ε 的需求是指数相关的，那么 cleary FPTAS 是 PTAS 的一个子案例，因为 1/ε 是多项式相关的 ( O(FPTAS) < O(PTAS ))
底线 - FPTAS 是 PTAS。