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ás and Meir (Oper Res Lett 11:19–21, 1992), there exists a cycle (tour) x₁,x₂,…,x_n through the n points, such that ∑i=1n|xi-xi+1|k^1/k≤c_k, where |x-y| is the Euclidean distance between x and y, and c_k is an absolute constant that depends only on k, where x_n+1≡x₁. 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 ∑i=1n|xi-xi+1|k^1/k=2^1/k·k. For the plane, the best constant is c₂=2 and this is the only exact value known. Bollobás and Meir showed that one can take c_k=923^1/k·k for every k≥3 and conjectured that the best constant is c_k=2^1/k·k, for every k≥2. Here we significantly improve the upper bound and show that one can take c_k=3523^1/k·k or c_k=2.91k(1+o_k(1)). Our bounds are constructive. We also show that c₃≥2^7/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ás–Meir conjecture is proposed.