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).