On a Traveling Salesman Problem for Points in the Unit Cube

Let X be an n-element point set in the k-dimensional unit cube [0,1]k where k ≥ 2. According to an old result of Bollob'as and Meir (1992), there exists a cycle (tour) x1, x2, ldots, xn through the n points, such that left(sumi=1n |xi - xi+1|k right)1/k ≤ ck, where |x-y| is the Euclidean distance between x and y, and ck is an absolute constant that depends only on k, where xn+1 equiv x1. From the other direction, for every k ≥ 2 and n ≥ 2, there exist n points in [0,1]k, such that their shortest tour satisfies left(sumi=1n |xi - xi+1|k right)1/k = 21/k · √k. For the plane, the best constant is c2=2 and this is the only exact value known. Bollob'as and Meir showed that one can take ck = 9 left(frac23 right)1/k · √k for every k ≥ 3 and conjectured that the best constant is ck = 21/k · √k, for every k ≥ 2. Here we significantly improve the upper bound and show that one can take ck = 3 √5 left(frac23 right)1/k · √k or ck = 2.91 √k (1+ok(1)). Our bounds are constructive. We also show that c3 ≥ 27/6, which disproves the conjecture for k=3. Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollob'as--Meir conjecture is proposed.