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]ᵏ [ 0 , 1 ] k where k ≥ 2 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ₙ x 1 , x 2 , … , x n through the n points, such that ( ∑ ᵢ₌₁ⁿ |xᵢ - xᵢ₊₁|ᵏ ) 1/k ≤ cₖ ∑ i = 1 n | x i - x i + 1 | k 1 / k ≤ c k , where $$|x-y|$$ | x - y | is the Euclidean distance between x and y , and cₖ c k is an absolute constant that depends only on k , where xₙ₊₁ ≡ x₁ x n + 1 ≡ x 1 . From the other direction, for every k ≥ 2 k ≥ 2 and n ≥ 2 n ≥ 2 , there exist n points in [0,1]ᵏ [ 0 , 1 ] k , such that their shortest tour satisfies ( ∑ ᵢ₌₁ⁿ |xᵢ - xᵢ₊₁|ᵏ ) 1/k = 21/k · √k ∑ i = 1 n | x i - x i + 1 | k 1 / k = 2 1 / k · k . For the plane, the best constant is c₂=2 c 2 = 2 and this is the only exact value known. Bollobás and Meir showed that one can take cₖ = 9 ( 2/3 ) 1/k · √k c k = 9 2 3 1 / k · k for every k ≥ 3 k ≥ 3 and conjectured that the best constant is cₖ = 21/k · √k c k = 2 1 / k · k , for every k ≥ 2 k ≥ 2 . Here we significantly improve the upper bound and show that one can take cₖ = 3 √5 ( 2/3 ) 1/k · √k c k = 3 5 2 3 1 / k · k or cₖ = 2.91 √k \ (1+oₖ(1)) c k = 2.91 k ( 1 + o k ( 1 ) ) . Our bounds are constructive. We also show that c₃ ≥ 27/6 c 3 ≥ 2 7 / 6 , which disproves the conjecture for $$k=3$$ 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.