Lower bounds for the universal TSP on the plane
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909437619339264 |
|---|---|
| author | Kravaris, Cosmas |
| author_facet | Kravaris, Cosmas |
| contents | We show a lower bound for the universal traveling salesman heuristic on the plane: for any linear order on the unit square $[0,1]^2$, there are finite subsets $S \subset [0,1]^2$ of arbitrarily large size such that the path visiting each element of $S$ according to the linear order has length $\geq C \sqrt{\log |S| / \log \log |S|}$ times the length of the shortest path visiting each element in $S$. ($C>0$ is a constant that depends only on the linear order.) This improves the previous lower bound $\geq C \sqrt[6]{\log |S| / \log \log |S|}$ of [HKL06]. The proof establishes a dichotomy about any long walk on a cycle: the walk either zig-zags between two far away points, or else for a large amount of time it stays inside a set of small diameter. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_16448 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lower bounds for the universal TSP on the plane Kravaris, Cosmas Metric Geometry Data Structures and Algorithms We show a lower bound for the universal traveling salesman heuristic on the plane: for any linear order on the unit square $[0,1]^2$, there are finite subsets $S \subset [0,1]^2$ of arbitrarily large size such that the path visiting each element of $S$ according to the linear order has length $\geq C \sqrt{\log |S| / \log \log |S|}$ times the length of the shortest path visiting each element in $S$. ($C>0$ is a constant that depends only on the linear order.) This improves the previous lower bound $\geq C \sqrt[6]{\log |S| / \log \log |S|}$ of [HKL06]. The proof establishes a dichotomy about any long walk on a cycle: the walk either zig-zags between two far away points, or else for a large amount of time it stays inside a set of small diameter. |
| title | Lower bounds for the universal TSP on the plane |
| topic | Metric Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.16448 |