algorithm - 1个近似算法可以用于多个NP-Hard问题吗？

Question

由于任何 NP Hard 问题都可以通过映射简化为任何其他 NP Hard 问题，所以我的问题向前迈出了 1 步；例如，该算法的每一步:是否也可以映射到另一个 NP 硬？

提前致谢

Answer 1

来自 http://en.wikipedia.org/wiki/Approximation_algorithm我们看到了

NP-hard 问题的可近似性差异很大；有些问题，例如装箱问题，可以在大于 1 的任何因子内进行近似(此类近似算法通常称为多项式时间近似方案或 PTAS)。其他的不可能在任何常数或多项式因子内近似，除非 P = NP，例如最大团问题。(结束引用)

由此可见，一个 NP 完全问题的良好近似不一定是另一个 NP 完全问题的良好近似。在那个幸运的世界里，我们可以使用容易近似的 NP 完全问题来为所有其他 NP 完全问题找到好的近似算法，但这里不是这种情况，因为存在难以近似的 NP 完全问题。