Metraipolis › archive › dc_fc70221fe8d8

Improved Euclidean Shallow Light Trees — arXiv:2608.03951

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.03951
License (as archived)
CC0-1.0
Archived
2026-10-31T13:09:35.431Z
SHA-256 of the archived text
4ac0e7485db2f454a147693179337555a4e8ae188ac3648c01a1d8851a43ddc4
Stable URL of this page
https://metraipolis.com/documento/dc_fc70221fe8d8

How to cite

Improved Euclidean Shallow Light Trees — arXiv:2608.03951 — arXiv (en), https://arxiv.org/abs/2608.03951 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fc70221fe8d8 (Metraipolis archive dc_fc70221fe8d8, sha256 4ac0e7485db2f454a147693179337555a4e8ae188ac3648c01a1d8851a43ddc4)
BibTeX
@misc{dcfc70221fe8d8,
  title = {Improved Euclidean Shallow Light Trees — arXiv:2608.03951},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.03951},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fc70221fe8d8; sha256 4ac0e7485db2f454a147693179337555a4e8ae188ac3648c01a1d8851a43ddc4},
  year = {2026}
}

Archived text

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

For parameters $\alpha,\beta \geq 1$, a spanning tree $T$ of a weighted graph $G$ rooted at a designated vertex $r$ is called an $(\alpha,\beta)$-shallow-light tree (SLT) if (i) for every vertex $v$, $d_T(r,v) \leq \alpha \cdot d_G(r,v)$ (root-stretch $\alpha$), and (ii) $w(T) \leq \beta \cdot w(\mathsf{MST})$ (lightness $\beta$). The pioneering work of Khuller, Raghavachari, and Young (SODA 1993) constructed $\left(1+\epsilon, \tfrac{2}{\epsilon}+1\right)$-SLTs for general weighted graphs, and proved that this tradeoff between root-stretch and lightness is tight even for series-parallel graphs. They further asked whether even a slight improvement, namely reducing the lightness to $\tfrac{2-c}{\epsilon}$ for any constant $c>0$, is possible in the Euclidean plane. We resolve this longstanding question in the affirmative. Specifically, we show that every Euclidean instance admits an SLT with root-stretch $1+\epsilon$ and lightness at most $\left(\frac{5}{3} + o_\epsilon(1)\right) \cdot \frac{1}{\epsilon}$, thereby significantly improving upon the longstanding $2/\epsilon$ barrier. As our second main result, we provide a construction of SLTs in the Euclidean plane, with root stretch $1+\epsilon$ and lightness at most $\left(\frac{2\pi}{\sqrt{4\pi^2+1}}+o_\epsilon(1)\right)\frac{1}{\epsilon} \approx (0.987+o_\epsilon(1))\frac{1}{\epsilon}$. Notably, this reduces the leading $2/\epsilon$ term in the lightness bound by more than a factor of two, and comes quite close to the lower bound of $\left(\frac{2\pi}{2\pi+1} +o_\epsilon(1))\right) \cdot \frac{1}{\epsilon} \approx (0.862 +o_\epsilon(1))\frac{1}{\epsilon}$ by Elkin and Solomon (FOCS 2011).

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-05 in cs.DS).
Categorie arXiv: Computational Geometry (cs.CG) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.03951 — 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-10-31T12:57:43.026Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).