Guardat en:
| Autors principals: | , , |
|---|---|
| Format: | Preprint |
| Publicat: |
2023
|
| Matèries: | |
| Accés en línia: | https://arxiv.org/abs/2310.02839 |
| Etiquetes: |
Afegir etiqueta
Sense etiquetes, Sigues el primer a etiquetar aquest registre!
|
| _version_ | 1866909241935134720 |
|---|---|
| author | Balogh, József Clemen, Felix Christian Dumitrescu, Adrian |
| author_facet | Balogh, József Clemen, Felix Christian Dumitrescu, Adrian |
| contents | Let $X$ be an $n$-element point set in the $k$-dimensional unit cube $[0,1]^k$ where $k \geq 2$. According to an old result of Bollobás and Meir (1992), there exists a cycle (tour) $x_1, x_2, \ldots, x_n$ through the $n$ points, such that $\left(\sum_{i=1}^n |x_i - x_{i+1}|^k \right)^{1/k} \leq 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 \geq 2$ and $n \geq 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(\frac23 \right)^{1/k} \cdot \sqrt{k}$ for every $k \geq 3$ and conjectured that the best constant is $c_k = 2^{1/k} \cdot \sqrt{k}$, for every $k \geq 2$. Here we significantly improve the upper bound and show that one can take $c_k = 3 \sqrt5 \left(\frac23 \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 \geq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_02839 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On a Traveling Salesman Problem for Points in the Unit Cube Balogh, József Clemen, Felix Christian Dumitrescu, Adrian Combinatorics Computational Geometry Discrete Mathematics Let $X$ be an $n$-element point set in the $k$-dimensional unit cube $[0,1]^k$ where $k \geq 2$. According to an old result of Bollobás and Meir (1992), there exists a cycle (tour) $x_1, x_2, \ldots, x_n$ through the $n$ points, such that $\left(\sum_{i=1}^n |x_i - x_{i+1}|^k \right)^{1/k} \leq 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 \geq 2$ and $n \geq 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(\frac23 \right)^{1/k} \cdot \sqrt{k}$ for every $k \geq 3$ and conjectured that the best constant is $c_k = 2^{1/k} \cdot \sqrt{k}$, for every $k \geq 2$. Here we significantly improve the upper bound and show that one can take $c_k = 3 \sqrt5 \left(\frac23 \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 \geq 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. |
| title | On a Traveling Salesman Problem for Points in the Unit Cube |
| topic | Combinatorics Computational Geometry Discrete Mathematics |
| url | https://arxiv.org/abs/2310.02839 |