💾 Archived View for breadpunk.club › ~pretzeltruck › log › circle-tsp.gmi captured on 2021-12-03 at 14:04:38. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

                         _           _ _                   _          
          _ __  _ __ ___| |_ _______| | |_ _ __ _   _  ___| | __  
         | '_ \| '__/ _ \ __|_  / _ \ | __| '__| | | |/ __| |/ /  
         | |_) | | |  __/ |_ / /  __/ | |_| |  | |_| | (__|   < 
         | .__/|_|  \___|\__/___\___|_|\__|_|   \__,_|\___|_|\_\
 .-.     |_|                  
 |_|__   _____________________ 2021-01-22 _______________________
 'O--O'-'-O----------------------------------------------------O-'

Circles and optimal TSP tours [Question]

Imagine the unit-circle [ C ] in the two-dimensional Euclidean plane. Let [ n ≥ 1 ] be a natural number and let [ S ⊂ C ] be a sample of the unit-cycle with [ |S| = n ] such that all points in the sample are equidistant, i.e., all points have exactly two nearest neighbors. The optimal TSP tour over [ S ] is produced by enumerating all points in clockwise or counter-clockwise order.

Let's take the set [ S ] and displace its members along their vectors. Let [ (z1, ..., zk), zi ∈ U[-Z,Z] ] be a vector of uniform random numbers in the interval [ [-Z,Z] ]. The set of displaced points [ D = { pi + zi pi : pi ∈ S } ] is then generated w.r.t. this vector of random numbers. Thus, the parameter combination [ (n, Z) ] generates an infinite set of TSP instances with [ (n, 0) ] corresponding to the TSP instances over sets [ S ].

Now the question:

Given parameters [ (n, Z) ], what is the probability that the optimal tour induced by [ S ] is also optimal for [ D ]?

I think this is a nice problem that could be dealt with empirically to establish an intuition and conjecture, then work on the proof afterwards. But maybe it has already been dealt with?