是否有固定的最壞情況錯誤會影響最遠插入?


11

對於旅行商問題的一些插入式試探法,我們有一個固定的最壞情況錯誤邊界形式:

$$ \ frac {z ^ H} {z ^ *} \ le \ eta,$$

其中, $ z ^ H $ 是啟發式方法針對給定實例返回的解決方案的目標值, $對於滿足三角形不等式的對稱實例,z ^ * $ 是該實例的最佳目標值,而 $ \ eta $ 是常數。

例如,最近插入具有固定的最壞情況界限 $ \ eta = 2 $ ,而最近鄰居可證明沒有固定的最壞情況界限 1

據我所知,最遠插入沒有固定的最壞情況界限,也沒有證明沒有這樣的界限。還是這樣,還是有最新的證據?

參考

1 D. J. Rosenkrantz,R。E. Stearns和P.M. Lewis II。分析旅行商問題的幾種啟發式方法。 SIAM Journal on Computing ,6(3):563-581,1977年。

7

To my knowledge, there is yet no known constant worst-case error bound $\eta$ for farthest insertion nor a proof that no constant bound exists. The results you mention here require symmetric TSP instances with costs that satisfy the triangle inequality, if I am not mistaken.

Nearest and cheapest insertion benefit from the fact that it can be shown that insertion steps are related in cost to costs on an underlying minimum spanning tree; thus, these heuristics perform with a worst-case upper bound that is the same as the twice-around MST heuristic. When selecting the farthest node to insert into the tour, this correspondence to the MST is not maintained.