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?