This question is closely related to this MO question.

I would like to know, whether any (planar Euclidean) TSP instances are known, that exhibit avalanche effects similar to those ecountered in sandpiles to which grains of sand are added one by one.

The planar Euclidean TSP analogy would be starting with the convex hull of the instance's pointset as the initial tour of size $k$ and then repeatedly expanding the tour by:

  • integrating as the point, the one, that incurs the least tour-elongation

  • restoring the optimality of the tour by exchanging a set of edges.

The avalanche effect would then correspond to the cardinality of the set of edges, that has to be exchanged in order to restore optimality of the tour after the next point had been integrated into the previous (optimal) tour.

Question: do there exist examples of infinite, discrete point sets of which only finitely many are on the convex hull, that exhibit avalanches of arbitrary size, if the next point is integrated, after the cuurent tour has been optimized.


Your Answer

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

Browse other questions tagged or ask your own question.