The Tight Competitive Ratio of Greedy for Online Steiner Forest

Abstract

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(lo{g}^{2}k)$-competitive and conjectured an $O(logk)$ 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)loglog(k))$. Specifically, we establish an $O(log(k)loglog(k))$ upper bound for arbitrary instances and construct a matching $\Omega (log(k)loglog(k))$ lower bound. Our results refute the $O(logk)$ conjecture of Awerbuch, Azar, and Bartal and establish a tight $\Theta (loglogk)$ separation between the greedy algorithm and the best possible online algorithm for Steiner Forest.