On a Traveling Salesman Problem for Points in the Unit Cube

Abstract

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 (1992), there exists a cycle (tour) $x_1,x_2,\dots ,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.