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

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 bound1.

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

1 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.

• That paper and others state the bound as 2ln(n)+.16 but I don't know of any work that either proves non-constant bound or gives a constant bound. Interesting hole in the literature (unless someone else comes up with a more recent reference)! jstor.org/stable/pdf/170036.pdf (Approximate Traveling Salesman Algorithms, Golden et al., Operations Research, 1980) is an older survey of these results. Jun 4, 2019 at 14:28
• Golden and Stewart, Empirical analysis of heuristics, 1985 is good too, for computational studies. Probably there's something more recent though. Jun 4, 2019 at 14:53
• It is a very funny coincidence that just this afternoon at the VeRoLog conference in Sevilla it was ( from an average performance point of view, not worst-case) discussed in one of the talks. It works quite well;) - not completely related to this question I know Jun 4, 2019 at 17:25
• Interesting! I knew it is reported to work well numerically. I like that because students always think at first that it's going to be bad (why would you want to choose the farthest point?!?) and then I get to tell them it's pretty good. :) Jun 4, 2019 at 17:37
• Some claim that farthest insertion works well on Euclidean instances because the initial insertion steps work to approximate a convex hull of the cities. An old result is that the cities on the convex hull of a set of Euclidean points are visited in the same order by the hull as the optimal TSP tour. Jun 4, 2019 at 20:56

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.

• Yes -- I forgot to add that the instances must be symmetric. I'll update my question. Jun 4, 2019 at 16:19

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.

• Interesting. So in other words we know that if there is a fixed worst-case bound, it can't be smaller than 2.43 for Euclidean instances or 6.5 for non-Euclidean. Jan 5, 2021 at 13:13