Metraipolis › archive › dc_d7b3ffb2a2d0

Optimal (Randomized) Compact Routing Schemes — arXiv:2611.04744

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04744
License (as archived)
CC0-1.0
Archived
2026-11-04T21:53:47.243Z
SHA-256 of the archived text
4005915985e4b0f7d134ff8b6dc111d876f2d4024dca62e5de7f8ff6019fa09e
Stable URL of this page
https://metraipolis.com/documento/dc_d7b3ffb2a2d0

How to cite

Optimal (Randomized) Compact Routing Schemes — arXiv:2611.04744 — arXiv (en), https://arxiv.org/abs/2611.04744 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d7b3ffb2a2d0 (Metraipolis archive dc_d7b3ffb2a2d0, sha256 4005915985e4b0f7d134ff8b6dc111d876f2d4024dca62e5de7f8ff6019fa09e)
BibTeX
@misc{dcd7b3ffb2a2d0,
  title = {Optimal (Randomized) Compact Routing Schemes — arXiv:2611.04744},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04744},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d7b3ffb2a2d0; sha256 4005915985e4b0f7d134ff8b6dc111d876f2d4024dca62e5de7f8ff6019fa09e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04744. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Compact routing schemes route messages along short paths while every vertex stores little information. We study the trade-off between the stretch and the storage of compact routing schemes in undirected graphs, in four models: labeled and name-independent schemes, with average or worst-case local storage. We improve the best known stretch in all four models. Our main result is a labeled routing scheme with expected stretch $2k-1$ and $\widetilde O(n^{1/k})$ average local storage, in which only the routing is randomized. Under the Erdős girth conjecture, no scheme with this storage has stretch below $2k-1$, so our scheme is optimal, up to polylogarithmic factors in the storage. With deterministic routing, we obtain stretch $\approx2.47k$, the best known deterministic stretch with average storage. Worst-case local storage is the classical setting of compact routing. The leading coefficient $4$ in the stretch $4k-5$ of Thorup and Zwick~[SPAA'01] was improved only by Chechik~[PODC'13], to $\approx3.68$ in unweighted graphs. In unweighted graphs, we obtain expected stretch $(\frac83k+O(1),O(k))$, and deterministic stretch $\approx3.05k$. Name-independent routing is harder, since the source knows only the name of the destination. The best known stretch with $\widetilde O(n^{1/k})$ local storage in unweighted graphs was $96k$, by Abraham, Gavoille, and Malkhi~[DISC'04]. We improve it by more than a factor of $8$. With average storage, we obtain expected stretch $4k-5$, which matches the labeled scheme of Thorup and Zwick. With worst-case storage in unweighted graphs, we obtain expected stretch $(8k+O(1),O(k))$. All our schemes for unweighted graphs extend to weighted graphs with a small loss in the stretch, and still improve the previous unweighted bounds.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.NI, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Networking and Internet Architecture (cs.NI).
Pagina del lavoro: https://arxiv.org/abs/2611.04744 — 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-04T21:39:19.535Z dalla pagina https://arxiv.org/list/cs.NI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).