Ordering tours in a Euclidean TSP according to (strictly) increasing length

37 Views Asked by At

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.

1

There are 1 best solutions below

2
On BEST ANSWER

This is not a complete answer, but since there are no other answers: if we have 4 points arranged in a square, this gives $d(h_2)/d(h_1)=\frac{2}{1+\sqrt{2}} $, and I have a feeling this is the best you can do.

I don't think that the minimum distance between any pair is the right place to look: it seems intuitive two swap the two edges adjacent to the shortest edge on $h_1$, but the increase in total length depends also on the angles between those edges, so there may be a "smallest" swap that does not involve the shortest edge.