algorithm - 是一个完全多项式时间近似方案一个多项式时间近似方案

Question

我想知道一个近似方案是否是一个完全多项式时间近似方案 - 它是否也是一个多项式时间近似方案？

例如，一个运行时间为 O(n²(1/ε)³)的近似方案——我们知道这是一个完全多项式时间的近似方案。

是否也是多项式时间逼近方案？谢谢!

这里有两个相关的问题(判断对错):

1. 对于任何固定的 ε>0，在 O(n 2/ε) 中运行的近似方案是完全多项式时间近似方案。
2. 对于任何固定的 ε>0，在 O(n2(1/ε)3)中运行的近似方案是多项式时间近似方案。

Answer 1

感谢您提出有趣的问题。我做了一些研究并想出了这个 very nice academic lecture关于 PTAS(多项式时间近似方案)和完全 PTAS。

如讲座中所述:

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。