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).