2
$\begingroup$

The paper [1] proves that, if we place $N$ points in the unit square, then the length $\ell$ of the euclidean TSP tour of those points must satisfy $$\ell \leq \sqrt{2N} + 7/4~~.$$ I'm wondering, can one also show that the length must satisfy $$\ell \leq 2\sqrt{N}~~?$$ Clearly, it will suffice to show that the desired result holds for $N\in\{3,\dots,8\}$ because it is obvious for $N=2$ and because $\sqrt{2N}+7/4 < 2\sqrt{N}$ provided $N>9$. I would imagine that one can do this with some kind of brute force computation, but my only worry is that some annoying difficulty may arise when $N=4$ because the proposed bound is tight.

[1] Few, L. "The shortest path and the shortest road through n points." Mathematika 2.02 (1955): 141-144.

Improve this question
$\endgroup$
1
  • $\begingroup$ This doesn't answer your question, but Chung and Graham have proof that one can take $\ell < .995\sqrt{N}$ for sufficiently large N. Also it is interesting to note that there is a lower bound of $(3/4)^{1/2}n^{1/2}+O(1)$ coming from a hexagonal lattice, perhaps one should check the small cases of this example. See: link.springer.com/article/10.1007%2FBF00149359. $\endgroup$
    – Mark Lewko
    Commented Sep 8, 2013 at 5:17

2 Answers 2

Reset to default
2
$\begingroup$

It seems possible. The examples which (to me) seem extreme with $N=3,4,5,6$ are ok and the gap is growing (starting at $N=4$) so perhaps estimation would suffice for the last two cases or perhaps they would not be hard to find exactly.

  • For $N=3$ one has $2\sqrt3-(2+\sqrt{2}) \approx 0.04988805$
  • For $N=4$ one has $2\sqrt4-4=0$
  • For $N=5$ one has $2\sqrt5-(3+2\sqrt{1/2} \approx 0.05792239$ (corners and center)
  • For $N=6$ one has $2\sqrt{6}-4.5 \approx 0.398979$

The last is more of a guess. It is the result of choosing the four corners and two points on the middle line so that the two paths shown are equal in length. Unexpectedly (to me) that puts the two internal points at $(\frac{4 \pm 1}{8},\frac{1}{2}).$ I suppose that the scaled $3-4-5$ right triangle is not so surprising.

enter image description here

Improve this answer
$\endgroup$
0
$\begingroup$

For n=6 the optimal solution is the four corners and two points on the diagonal, roughly at (0.4, 0.4) and (0.6, 0.6). The optimal length is 4.571326...

There are newer results than the 1955 paper, see for example Howard J. Karloff: How long can a Euclidean traveling salesman tour be? SIAM Journal on Discrete Mathematics, 2(1):91--99, 1989.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .