MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Generalized Euclidean TSP

Suppose I have n sets $X_1,\dots,X_n$ consisting of $k$ points each, where all $nk$ points are i.i.d. uniform random samples in the unit square $[0,1]\times[0,1]$. Consider the shortest path that goes through at least one element of each set $X_i$. Is the asymptotic behavior of this, a la the Beardwood-Halton-Hammersley (BHH) theorem, well-known? (By "asymptotic behavior", I mean, assume that $k$ is fixed and look at what happens as $n$ becomes large)

-
Looks like a great question, but what is BHH theorem? – Gil Kalai Mar 1 2011 at 17:55
Beardwood-Halton-Hammersley. It says that, when $k=1$ in my problem (i.e. the shortest path through $n$ uniformly sampled points), the path length scales with $\sqrt{n}$: myweb.lsbu.ac.uk/~whittyr/MathSci/TheoremOfTheDay/… – John Gunnar Carlsson Mar 1 2011 at 17:58
What is the link between $k$ and $n$ ? – camomille Mar 1 2011 at 18:40
I'm assuming that $k$ is fixed, and we're looking at the behavior as $n$ goes to infinity. – John Gunnar Carlsson Mar 1 2011 at 18:53
There is a transformation of the GTSP to the TSP, the Laporte-Semet transformation. It doubles the number of vertices. Perhaps this could be a route to obtain a result? [G. Laporte, F. Semet, "Computational evaluation of a transformation procedure for the symmetric generalized traveling salesman problem," INFOR (37) 1999 114–120.] – Joseph O'Rourke Mar 1 2011 at 19:26
show 1 more comment

You should be able to get $O(\sqrt{n/k})$ by choosing a smaller square of area $1/k$, which will contain one point from most of the point sets, and use the BHH theorem to find a TSP tour of this. Now, you have to show that adding the points from the point sets you left out doesn't increase the length of the tour much. It certainly won't increase it by more than a $\sqrt{\log n}$ factor, because a square $\log n$ times larger in area will with high probability contain a point from all the point sets, and choosing one point randomly from each of the point sets in that square gives points uniform in this square. I'd guess the tour length will still be $O(\sqrt{n/k})$, but you may have to do some work to prove this. On the other hand you certainly can't do better than this, because you need $n$ points in your tour, and the typical distance from one point to its nearest neighbor is $O(1/\sqrt{nk})$.
Here's a strategy for a proof of $O(\sqrt{n/k})$. First take a square of area $\alpha /k$, with $\alpha$ chosen so that this contains $9/10\, n$ of the classes of points. The BHH theorem shows you can find a TSP tour of this square with length $O(\sqrt{n/k})$. Now, we need to show adding the rest of the points doesn't increase the tour length very much.
We'll find subsquares $S_1$, $S_2$, $S_3$, $\ldots$, $S_{\log n}$ where the $i$'th square is big enough that the expected number of classes of points it contains is $(1-1/10^{i})n$. The area of the $i$'th square will be $\alpha i /k$ for some constant $\alpha$. To get a TSP of the $9/10^in$ new classes of points in the $i$'th square takes length $O\left(\sqrt{i 9/10^i n/k}\right)$. The series sums to $O(\sqrt{n/k})$.