Metraipolis › archive › dc_21ebcb2c66eb

A Better Lower Bound for Sublinear Metric Steiner Tree — arXiv:2610.41666

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41666
License (as archived)
CC0-1.0
Archived
2026-11-03T08:24:08.164Z
SHA-256 of the archived text
4ef33baaf6d400da91d0bc6e1b1b2b0ba25969af83214f8c210398d532d23328
Stable URL of this page
https://metraipolis.com/documento/dc_21ebcb2c66eb

How to cite

A Better Lower Bound for Sublinear Metric Steiner Tree — arXiv:2610.41666 — arXiv (en), https://arxiv.org/abs/2610.41666 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_21ebcb2c66eb (Metraipolis archive dc_21ebcb2c66eb, sha256 4ef33baaf6d400da91d0bc6e1b1b2b0ba25969af83214f8c210398d532d23328)
BibTeX
@misc{dc21ebcb2c66eb,
  title = {A Better Lower Bound for Sublinear Metric Steiner Tree — arXiv:2610.41666},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41666},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_21ebcb2c66eb; sha256 4ef33baaf6d400da91d0bc6e1b1b2b0ba25969af83214f8c210398d532d23328},
  year = {2026}
}

Archived text

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

In the metric Steiner tree problem, we are given an $n$-point metric space $(V,w)$ and a set of terminals $T\subseteq V$, and we are interested in the smallest total weight $\mathsf{st}(V,T,w)$ of a tree that contains every terminal and may also use points of $V\setminus T$. We work in the distance-oracle model: the algorithm knows $V$ and $T$ in advance and learns $w$ only by querying a single entry $w(u,v)$ at a time. The goal is to estimate $\mathsf{st}(V,T,w)$ with the minimum number of queries. A factor of $2$ is achievable with nearly linear number of queries, so the interesting question is the query complexity of algorithms with an approximation ratio strictly below $2$. We prove that for every fixed $\eta\in(0,1)$, every randomized $(2-\eta)$-approximation algorithm must make more than $\widetilde{\Omega}(n^{7/5})$ queries, improving upon the previously known bound of $\widetilde{\Omega}(n^{6/5})$. Given that the best known upper bound shows that $\widetilde O(n^{5/3})$ queries suffice, the exponent of this problem now lies between $7/5$ and $5/3$, up to logarithmic factors.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.41666 — 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-03T08:07:53.812Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).