Let X be an n-element point set in the k-dimensional unit cube \([0,1]^k\) where \(k \ge 2\) . According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour) \(x_1, x_2, \ldots , x_n\) through the n points, such that \(\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le 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} \equiv x_1\) . From the other direction, for every \(k \ge 2\) and \(n \ge 2\) , there exist n points in \([0,1]^k\) , such that their shortest tour satisfies \(\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}\) . For the plane, the best constant is \(c_2=2\) and this is the only exact value known. Bollobás and Meir showed that one can take \(c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}\) for every \(k \ge 3\) and conjectured that the best constant is \(c_k = 2^{1/k} \cdot \sqrt{k}\) , for every \(k \ge 2\) . Here we significantly improve the upper bound and show that one can take \(c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}\) or \(c_k = 2.91 \sqrt{k} \ (1+o_k(1))\) . Our bounds are constructive. We also show that \(c_3 \ge 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.
