pipette
ENEnglish

The Tight Competitive Ratio of Greedy for Online Steiner Forest

Iman Gholami, Ilya Hajiaghayi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade

Preprint

En palabras de los autores

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 -competitive and conjectured an bound, where is the number of terminal pairs. Bamas, Drygala, and Maggiori (SODA 2022) obtained an 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 . Specifically, we establish an upper bound for arbitrary instances and construct a matching lower bound. Our results refute the conjecture of Awerbuch, Azar, and Bartal and establish a tight separation between the greedy algorithm and the best possible online algorithm for Steiner Forest.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.