💾 Archived View for breadpunk.club › ~pretzeltruck › log › circle-tsp.gmi captured on 2021-11-30 at 19:37:34. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
_ _ _ _
_ __ _ __ ___| |_ _______| | |_ _ __ _ _ ___| | __
| '_ \| '__/ _ \ __|_ / _ \ | __| '__| | | |/ __| |/ /
| |_) | | | __/ |_ / / __/ | |_| | | |_| | (__| <
| .__/|_| \___|\__/___\___|_|\__|_| \__,_|\___|_|\_\
.-. |_|
|_|__ _____________________ 2021-01-22 _______________________
'O--O'-'-O----------------------------------------------------O-'
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?