近似算法是否与多项式时间近似算法 (PTAS) 相同？例如，可以证明 A(I) <= 2 * OPT(I) 用于顶点覆盖。这是否意味着 Vertex Cover 具有 2多项式时间逼近算法或 PTAS？
谢谢！
注意：斜体字是我发布问题后所做的编辑。
2 回答
1
不，不一定是这样。PTAS 是一种算法，其中给定任何 ε > 0，您可以在多项式时间内将答案近似为 (1 + ε) 的因子。换句话说，您可以获得任意好的近似值。
一些已知问题（例如，MAX-3SAT）具有针对特定因子（例如，5/8）的近似算法，但已知除非 P = NP，否则问题的近似程度存在硬性限制在多项式时间内。例如，PCP 定理说 MAX-3SAT 没有多项式时间 7/8 近似，除非 P = NP。因此，MAX-3SAT 可能具有 PTAS，但前提是 P = NP。
希望这可以帮助！
于 2014-04-19T07:28:21.770 回答
1
具有 2 近似算法的顶点覆盖与具有 PTAS 算法的顶点覆盖不同。有时，有些问题可以进行更好的近似。然后这些问题承认 PTAS。
此类算法将问题的一个实例作为输入，另一个输入参数epsilon >0。它给出了一个输出，其值最多为(1+ epsilon ).OPT用于最小化问题；和 (1/(1+ epsilon )).OPT 用于最大化问题。
PTAS 算法的运行时间是n（问题实例的大小）的多项式。有时，运行时也是epsilon中的多项式，然后调用它来承认 FPTAS（完全 PTAS）。
示例： 具有整数利润的 KNAPSACK 动态规划算法给出了最优解。而具有实值利润的 KNAPSACK 问题不承认多项式时间算法。但它承认 FPTAS，将实际价值利润转换为整数利润；DP算法用于计算具有“四舍五入”利润的解决方案。
另一个例子，Max Independent Set不承认 PTAS 或 FPTAS。因为在这种情况下，我们可以为epsilon设置一个值，这将始终为使用该 PTAS 算法的任何图提供最佳解决方案；这在 P=NP 之前是不可能的。
于 2015-12-04T22:10:07.383 回答