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, 2018 at 12:38


Your Answer

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

Browse other questions tagged or ask your own question.