Metraipolis › archive › dc_19ef91c27308
The Tight Competitive Ratio of Greedy for Online Steiner Forest — arXiv:2610.40569
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.40569
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:47:47.374Z
- SHA-256 of the archived text
215a1947b4f1d39890bd1d469e2ef067d38f1c3f9f3bc1be9b2bfa1bb8e92496- Stable URL of this page
https://metraipolis.com/documento/dc_19ef91c27308
How to cite
The Tight Competitive Ratio of Greedy for Online Steiner Forest — arXiv:2610.40569 — arXiv (en), https://arxiv.org/abs/2610.40569 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_19ef91c27308 (Metraipolis archive dc_19ef91c27308, sha256 215a1947b4f1d39890bd1d469e2ef067d38f1c3f9f3bc1be9b2bfa1bb8e92496)
BibTeX
@misc{dc19ef91c27308,
title = {The Tight Competitive Ratio of Greedy for Online Steiner Forest — arXiv:2610.40569},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.40569},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_19ef91c27308; sha256 215a1947b4f1d39890bd1d469e2ef067d38f1c3f9f3bc1be9b2bfa1bb8e92496},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.40569. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The online Steiner Forest problem is a fundamental network design problem in which terminal pairs arrive one at a time and an algorithm must irrevocably purchase edges connecting each pair. The natural greedy algorithm connects each terminal pair by a shortest path after making all previously purchased edges free. Awerbuch, Azar, and Bartal (SODA 1996) proved that this algorithm is $O(log^2 k)$-competitive and conjectured an $O(log k)$ bound, where $k$ is the number of terminal pairs. Bamas, Drygala, and Maggiori (SODA 2022) obtained an $O(\log \NumPairs\log\log \NumPairs)$ bound for greedy on a restricted class of inputs, leaving the general case open. In this paper, we resolve the competitive ratio of the greedy algorithm for online Steiner Forest, proving that it is tightly $\Theta(log(k) log log(k))$. Specifically, we establish an $O(log(k) log log(k))$ upper bound for arbitrary instances and construct a matching $\Omega(log(k) log log(k))$ lower bound. Our results refute the $O(log k)$ conjecture of Awerbuch, Azar, and Bartal and establish a tight $\Theta(log log k)$ separation between the greedy algorithm and the best possible online algorithm for Steiner Forest. 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.40569 — 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-01T02:17:58.608Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).