0
$\begingroup$

It is known that tour expansion is a rather poor heuristic for generating short Hamilton cycles even in the planar Euclidean case. That comes as a surprise when learning of that for the first time.
The surprise is due to the fact that the heuristic seems to resemble complete induction if one starts with the convex hull of the pointset as the base case and then inserts as the next point the one that incurs the least length-increase of the tour:

base case:

  • the relative order of the points on the convex hull is the same as in the shortest tour through all points.

induction step:

  • if the the tour $T_n$ through the first $\left|CH\right|+n$ points is optimal, then the shortest tour $T_{n+1}$ through one additional point is again optimal ($\left|CH\right|$ shall be the number of points on the convex hull and $n\geq 0)$.

Question:

What are the reasons that prove that greedy tour expansion is not a variant of complete induction?


What I am looking for is a proof that clearly indicates, which of the conditions for the applicability of complete induction are violated by greedy tour expansion.

$\endgroup$
3
  • $\begingroup$ "then inserts as the next point the one that incurs the least length-increase of the tour:" Meaning "inserts between 2 adjacent points in the existing tour" or something else? $\endgroup$
    – fedja
    Jan 25, 2020 at 18:20
  • $\begingroup$ @fedja yes, that is the tour expansion heuristic, so that the relative order of points isn't changed by later insertions. $\endgroup$ Jan 25, 2020 at 18:31
  • $\begingroup$ the greedy tour expansion corresponds to th CHCI heuristic described and analyzed in Investigating TSP Heuristics for Location-Based Services $\endgroup$ Jan 25, 2020 at 19:21

0

Your Answer

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