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?

  • $\begingroup$ What is your measure of how good a path is? $\endgroup$ – Douglas Zare Sep 1 '16 at 7:47
  • $\begingroup$ I want the path to have a short Euclidean length. Presumably I'd need to search all $n!$ permutations to get the shortest path, so I'd just like the Euclidean length to be "not too much longer" in some probabilistic sense. (made some minor edits to the original question to try to clarify this) $\endgroup$ – Tom Solberg Sep 1 '16 at 7:55
  • $\begingroup$ Yes, it was clear that you wanted it to be short. How are you measuring whether a path of a given shortness is good? $\endgroup$ – Douglas Zare Sep 1 '16 at 8:00
  • $\begingroup$ @DouglasZare oh, I see -- well, given that the length of the shortest path scales proportionally to $\sqrt{n}$, I'd like a path whose length is less than $c\sqrt{n}$, for some value of $c$. Does that make sense? $\endgroup$ – Tom Solberg Sep 1 '16 at 8:13
  • $\begingroup$ Did you check, or is there an obstruction to checking, that picking your subset at random usually works? $\endgroup$ – usul Sep 1 '16 at 11:57

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.