On a Traveling Salesman Problem for Points in the Unit Cube

Balogh, József; Clemen, Felix Christian; Dumitrescu, Adrian

doi:10.1007/s00453-024-01257-w

Abstract LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$

{[0, 1]}^{k}

where$$k \ge 2$$

k \geq 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$$

x_{1}, x_{2}, \dots, x_{n}

through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$

{(\sum_{i = 1}^{n}, {| x_{i} - x_{i + 1} |}^{k})}^{1 / k} \leq c_{k}

, where$$|x-y|$$

| x - y |

is the Euclidean distance betweenxandy, and$$c_k$$

c_{k}

is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$

x_{n + 1} \equiv x_{1}

. From the other direction, for every$$k \ge 2$$

k \geq 2

and$$n \ge 2$$

n \geq 2

, there existnpoints in$$[0,1]^k$$

{[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}$$

{(\sum_{i = 1}^{n}, {| x_{i} - x_{i + 1} |}^{k})}^{1 / k} = 2^{1 / k} \cdot \sqrt{k}

. For the plane, the best constant is$$c_2=2$$

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}$$

c_{k} = 9 {(\frac{2}{3})}^{1 / k} \cdot \sqrt{k}

for every$$k \ge 3$$

k \geq 3

and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$

c_{k} = 2^{1 / k} \cdot \sqrt{k}

, for every$$k \ge 2$$

k \geq 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}$$

c_{k} = 3 \sqrt{5} {(\frac{2}{3})}^{1 / k} \cdot \sqrt{k}

or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$

c_{k} = 2.91 \sqrt{k} (1 + o_{k} (1))

. Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$

c_{3} \geq 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.

More Like this