逼近算法競爭問題

Question

假設一個爲O（n 2 ）-time的α-近似算法存在對於以下每個對的兩個問題中的一個：

• 點覆蓋和獨立設置
• 獨立設置並派
• 最大流和最小割

這是否保證一個爲O（n ）時間阿爾法近似算法存在的對中的其他問題？我知道Clique減少爲獨立集，而獨立集又減少到頂點覆蓋。

Answer 1

不一定，有兩個原因。

首先，NP減少通常在複雜度上不是線性的。其中一些是，但通常是一個複雜的問題n會減少到一些其他NP問題的大小n^3什麼的。即使我們發現線性時間3SAT算法，我們也不會爲所有NP難題找到線性時間算法 - 只是多項式算法。所以如果「相似」，你的意思是「也n^2」，而不是一般。

其次，近似值通常不會傳遞。由於複雜性的非線性增長（這是對原因的簡化，但它會這樣做），近似保證通常無法在還原過程中存活。因此，雖然所有NP完全問題在某種意義上都是具有精確溶解硬度的同志，但它們在近似硬度方面遠非如此。

在某些特定情況下，近似值做轉移（以及您的一個例子 - 作爲讀者的練習 - 絕對轉移）。但它不能保證。