對於旅行商問題的一些插入式試探法，我們有一個固定的最壞情況錯誤邊界形式：
$$ \ 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年。
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.
