一千萬個為什麽

搜索

為什麽Metric TSP的最佳可能達到的近似比率被認為是4/3?

是否只是特定實例的完整性差距(LP/IP)不超過4/3?先驗謝謝。

最佳答案

據我所知,這是唯一的原因,我不確定這些領域的每個人是否同意這一點。

樂觀的推理是:由於在獲得更大的下限方面沒有任何進展,$ 4/3 $是正確的約束。一旦我們確切知道這一點,我們“只”需要一個多項式時間舍入算法。

更悲觀的人只會將$ 4/3 $視為下限。要打敗這個, 你需要一種不會“使用”Held-Karp松弛的算法,即使不是以隱藏的方式。

更悲觀的人會說3美元/ 2美元是正確的約束,因為沒有人可以改進Christofides算法(忽略一些最近的進展。)

請註意,對於公制ATSP,完整性差距至少為$ 2 - \ epsilon $ (Charikar,Goemans,Karloff,FOCS 2004)

轉載註明原文: 為什麽Metric TSP的最佳可能達到的近似比率被認為是4/3?