Is there a fixed worst-case error bound for farthest-insertion?

Question

For some insertion-type heuristics for the traveling salesman problem, we have a fixed worst-case error bound of the form:

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

where $z^H$ is the objective value of the solution returned by the heuristic for a given instance, $z^*$ is the optimal objective value for that instance, and $\eta$ is a constant, for symmetric instances satisfying the triangle inequality.

For example, nearest-insertion has a fixed worst-case bound of $\eta=2$, while nearest-neighbor provably has no fixed worst-case bound¹.

As far as I know, farthest insertion has no fixed worst-case bound, nor has it been proven that no such bound exists. Is this still true, or is there a more recent proof?

Reference

_{¹ D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis II. An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3):563–581, 1977.}

Answer 1

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.

Answer 2

The question is still open and interesting.

In my contribution to IPCO-2, Pittsburgh, 1992, I provided a family of examples of a Euclidean instance with a worst case ratio approaching $2.43$ and a non-Euclidean one with ratio approaching $6.5$.

An easy example of a Euclidean instance with a bad Farthest Insertion result is constructed by considering an infinite number of cities along the edges of two squares $S_1$ and $S_2$ where \begin{align}S_1&=\{(x,y)\mid|x|+|y|\le2\land(|x|=1\vee|y|=1)\}\\S_2&=(1+\epsilon)\cdot S_1.\end{align} Choosing $\epsilon$ sufficiently small gives a ratio of approximately $1.73$. The Farthest Insertion tour will cross from $S_1$ to $S_2$ and back multiple times.