Finding a short path using $(0.99n)!$ permutations

Question

Suppose I have $n$ points $x_1,\dots,x_n$ that are all independent uniform samples in the unit square, and I'd like to find a short path (in terms of Euclidean length) that touches all of them (a traveling salesman path, in other words). Obviously, one (inefficient) way to do this would be to write down every permutation of $\{1,\dots,n\}$, record the length of the path that visits the $x_i$'s in that order, and select the permutation that gave the shortest path.

Now suppose that, before the $x_i$'s are sampled, I am allowed to write down not all $n!$ permutations, but only a subset of permutations of size (say) $(0.99n)!$. Is there a "clever" choice of permutations that is likely to contain a good (i.e. short) path (in the sense of Euclidean length) through the $x_i$'s, in the limit as $n$ becomes large?

Answer 1

That is highly unlikely. Take any such system $S$ of permutations. Take any configuration of points obtained by sampling and note that we can also get it with the points re-enumerated in any way. Now let us look at how many reasonably short path enumerations are there at all. For each short path, there is a sequence of integers $a_1,\dots,a_{n-1}$ with sum $\le Cn$ such that the $k$-th step jump is at most $a_k n^{-1/2}$. There are only exponentially (in $n$) many such sequences. Now, for a typical configuration, the number of points in any disk of radius $Rn^{-1/2}$ is at most $CR^2\log n$ (the exponential tail estimate for the Poisson distribution), so at each step we have just $Ca_k^2\log n$ choices at most, giving at most $e^{Cn}(\log n)^n$ permutations total that can work in principle. Call that set $K$. We must have $S\pi\cap K\ne\varnothing$ for most permutations $\pi$, whence $|S||K|\ge n!/2$. So, we can have only $(C\log n)^n$ gain (actually even less; I guess the exponential gain is the right one), which is quite short of $n^{0.01n}$ you want.