# 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. – Michael Trick Jun 4 '19 at 14:28
• Golden and Stewart, Empirical analysis of heuristics, 1985 is good too, for computational studies. Probably there's something more recent though. – LarrySnyder610 Jun 4 '19 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 – Albert Schrotenboer Jun 4 '19 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. :) – LarrySnyder610 Jun 4 '19 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. – alerera Jun 4 '19 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.