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

Question

由于任何NP困难问题都可以通过映射简化为任何其他NP困难问题，因此我的问题是前进一步；例如，算法的每一步:这也可以映射到其他NP困难问题吗？

提前感谢

Answer 1

从http://en.wikipedia.org/wiki/Approximation_algorithm我们可以看到

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

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

Answer 2

当证明一个问题是NP-Hard时，我们通常考虑该问题的决策版本，其输出要么是yes，要么是no。然而，当考虑近似算法时，我们考虑问题的优化版本。

如果你使用一个问题的近似算法来解决另一个问题，通过使用NP-Hard证明中的约简，近似比可能会改变。例如，如果你对问题A有一个2-近似算法，并用它来解决问题B，那么你可能会得到一个问题B的O(n)-approximation算法，因为约简不会保持近似比。因此，如果你想使用一个问题的近似算法来解决另一个问题，你需要确保约简不会改变太多的近似比，以便得到一个有用的算法。例如，您可以使用L-reduction或PTAS reduction。