1. On a Traveling Salesman Problem for Points in the Unit Cube.
- Author
-
Balogh, József, Clemen, Felix Christian, and Dumitrescu, Adrian
- Subjects
- *
TRAVELING salesman problem , *CUBES , *EUCLIDEAN distance , *POINT set theory , *ASSIGNMENT problems (Programming) - Abstract
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 ∑ i = 1 n | 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 ∑ i = 1 n | 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 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 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 . 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. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF