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 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 through the $x_i$'s, in the limit as $n$ becomes large?