Let $H$ be the set of all Hamiltonian cycles on the complete graph $K_n$ associated with a set of $n \geq 4$ points $P$ in the plane where edge weights are defined using the Euclidean distance between pairs of points in $P$. Suppose that $h_1 \in H$ is an optimal tour with length $d(h_1)$ and that the tours are numbered in order of increasing length so that: $d(h_1) \leq d(h_2) \leq \cdots \leq d(h_{|H|})$.

Question: Is there a set of conditions on the set of points in $P$ that would result in the ordering above being a sequence of strict inequalities? I am interested in finding a lower bound $\lambda < 1$ that characterizes the ratio $d(h_1) / d(h_2) < \lambda$ given some distribution of points, if possible. Intuitively it seems this may be related to the minimum distance between any pair of points in $P$, or the minimum difference in tour length resulting from an edge swap. Perhaps there are some other well known results on the distribution of tour lengths that might be related. I would be grateful for any references that come to mind on topics related to this question.

  • $\begingroup$ One of the inequalities is wrongly stated (currently, they are contradictory). $\endgroup$ – Gamow Nov 27 '18 at 12:38

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.