arXiv · Oct 29, 2026
The Tight Competitive Ratio of Greedy for Online Steiner Forest
By Iman Gholami, Ilya Hajiaghayi, MohammadTaghi Hajiaghayi et al.
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² 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 NumPairsloglog 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 Θ(log(k) log log(k)). Specifically, we establish an $O(log(k) log log(k))$ upper bound for arbitrary instances and construct a matching Ω(log(k) log log(k)) lower bound. Our results refute the $O(log k)$ conjecture of Awerbuch, Azar, and Bartal and establish a tight Θ(log log k) separation between the greedy algorithm and the best possible online algorithm for Steiner Forest.