Metraipolis › archive › dc_2d72360eb50b
An $n^{0.3+\varepsilon}$-Approximation for Steiner $k$-Forest — arXiv:2610.09932
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.09932
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T12:49:44.199Z
- SHA-256 of the archived text
6ce4c98d97a5d1a2a0432d3e69360bf3dffeb4f729c3188b4467c3d7b4b4d646- Stable URL of this page
https://metraipolis.com/documento/dc_2d72360eb50b
How to cite
An $n^{0.3+\varepsilon}$-Approximation for Steiner $k$-Forest — arXiv:2610.09932 — arXiv (en), https://arxiv.org/abs/2610.09932 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2d72360eb50b (Metraipolis archive dc_2d72360eb50b, sha256 6ce4c98d97a5d1a2a0432d3e69360bf3dffeb4f729c3188b4467c3d7b4b4d646)
BibTeX
@misc{dc2d72360eb50b,
title = {An $n^0.3+varepsilon$-Approximation for Steiner $k$-Forest — arXiv:2610.09932},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.09932},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2d72360eb50b; sha256 6ce4c98d97a5d1a2a0432d3e69360bf3dffeb4f729c3188b4467c3d7b4b4d646},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09932. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We give an $n^{0.3+\varepsilon}$-approximation algorithm for the Steiner $k$-Forest problem, for any constant $\varepsilon>0$. As a function of $n$, this improves over the $O(\min\{\sqrt{n},\sqrt{k}\})$-approximation of Gupta et al. [ESA'07, TALG'10] which has stood for nearly two decades for the general case, as well as the later $n^{0.448}$-approximation of Dinitz et. al [APPROX-RANDOM'14, TALG'17] for the uniform weight case. On the other hand, we show that, due to lower bounds on the Densest $k$-Subgraph problem, the $O(\sqrt k)$-approximation for Steiner $k$-Forest likely cannot be improved. Specifically, we show that for any sufficiently small $\varepsilon>0$, an $O(k^{1/2-\varepsilon})$-approximation for Steiner $k$-Forest would surpass known degree-$n^{\Omega(\varepsilon^2)}$ Sum-of-Squares integrality gaps for Densest k-Subgraph and refute the corresponding dense-versus-random conjecture.
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.09932 — 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-08T12:19:30.204Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).