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_1, x_2, . . . , x_n$ through the n points, such that $(∑^n_{i=1} |x _i − x_{i+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_1$ . 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 $(∑^n_{ i=1} |x_i − x_{ i+1}|\ ^k )^{1/k} = 2^{1/k} · √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 ( \frac{2}{3} )^{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 = 3√5 ( \frac{2}{3} )^{1/k} · √k$ or $c_k = 2.91√k (1 + o_k (1))$. Our bounds are constructive. We also show that $c_3 ≥ 2 ^{7/6}$, which disproves the conjecture for $k = 3$. ... mehrConnections 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.