11
$\begingroup$

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.

$\endgroup$
5
  • 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, 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$ 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$ 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$ 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
    Jun 4, 2019 at 20:56

2 Answers 2

8
$\begingroup$

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.

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

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.

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

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .