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$ Jun 4 '19 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$
    – LarrySnyder610
    Jun 4 '19 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$ Jun 4 '19 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$
    – LarrySnyder610
    Jun 4 '19 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
    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.

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$
    – LarrySnyder610
    Jun 4 '19 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$
    – LarrySnyder610
    Jan 5 '21 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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