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\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,...,x_n$ through the n points, such that $({\sum }_{i=1}^n|x_i-x_{i+1|}{}^k{)}^{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 $({\sum }_{i=1}^n|x_i-x_{i+1}|{}^k{)}^{1/k}=2^{1/k}·\surd 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}·\surd k$ for every $k\ge 3$ and conjectured that the best constant is $c_k=2^{1/k}·\surd k$, for every $k\ge 2$. Here we significantly improve the upper bound and show that one can take $c_k=3\surd 5(\frac{2}{3}{)}^{1/k}·\surd k$ or $c_k=2.91\surd 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$. ... 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.