Metraipolis › archive › dc_8c5fa5c028de
The Value of Steiner Hubs in Two-Hop Distance Labeling — arXiv:2611.01106
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.01106
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:38:25.044Z
- SHA-256 of the archived text
30c25d5b92fd40a195a3fe1e12428d3aaf8c0cb75f09e5c536e15d7c4fd50c79- Stable URL of this page
https://metraipolis.com/documento/dc_8c5fa5c028de
How to cite
The Value of Steiner Hubs in Two-Hop Distance Labeling — arXiv:2611.01106 — arXiv (en), https://arxiv.org/abs/2611.01106 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8c5fa5c028de (Metraipolis archive dc_8c5fa5c028de, sha256 30c25d5b92fd40a195a3fe1e12428d3aaf8c0cb75f09e5c536e15d7c4fd50c79)
BibTeX
@misc{dc8c5fa5c028de,
title = {The Value of Steiner Hubs in Two-Hop Distance Labeling — arXiv:2611.01106},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.01106},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8c5fa5c028de; sha256 30c25d5b92fd40a195a3fe1e12428d3aaf8c0cb75f09e5c536e15d7c4fd50c79},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01106. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Two-hop distance labelings were introduced in 2002 by Cohen, Halperin, Kaplan, and Zwick with hubs of two kinds: vertices of the graph, or, in their Steiner variant, arbitrary objects carrying arbitrary real values. On no family is the value of that freedom known. We determine it on $\ell_1$ products of betweenness-free metrics, those with no point between two others, a class containing every Hamming graph. The freedom is worth nothing when the factors have at most three letters, while from four letters on the largest saving is polynomial in the size of the product, attained on products of positively weighted stars. The $d$-dimensional hypercube is the two-letter case, and labeling it takes $(5/2+o(1))^d$ entries even with arbitrary hubs, matching the vertex-hub optimum of Goldberg, Razenshteyn, and Savchenko. Every lower bound here comes from one semidefinite program on a single factor, whose value $\Lambda$ never exceeds the rate that vertex hubs already achieve on the Hamming graph; where $\Lambda$ meets that ceiling, the freedom is worth nothing, and the ceiling is met exactly up to three letters. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno). Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2611.01106 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-03T11:05:22.344Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).