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?


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.

  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jun 4, 2019 at 14:28
  • 1
    $\begingroup$ Golden and Stewart, Empirical analysis of heuristics, 1985 is good too, for computational studies. Probably there's something more recent though. $\endgroup$ Commented Jun 4, 2019 at 14:53
  • $\begingroup$ 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 $\endgroup$ Commented Jun 4, 2019 at 17:25
  • $\begingroup$ 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. :) $\endgroup$ Commented Jun 4, 2019 at 17:37
  • 1
    $\begingroup$ 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. $\endgroup$
    – alerera
    Commented Jun 4, 2019 at 20:56

2 Answers 2


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.

  • $\begingroup$ Yes -- I forgot to add that the instances must be symmetric. I'll update my question. $\endgroup$ Commented 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.

  • $\begingroup$ 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. $\endgroup$ Commented Jan 5, 2021 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.