Greedy algorithm for online network design has precise performance limits
The Tight Competitive Ratio of Greedy for Online Steiner Forest
Data Structures and Algorithms
Summary
The problem is about connecting pairs of points in a network as they show up, without knowing future pairs. The greedy algorithm connects each pair along the shortest available path, using edges already bought for free. Previously, it was known this greedy method was somewhat inefficient, but the exact inefficiency was unknown. The authors show the greedy algorithm’s performance is precisely bounded by a factor involving log(k) times log log(k), where k is the number of pairs. This settles a long-standing question about how well the greedy method can do compared to the best possible approach.
What this means in practice
- •For network engineers: Determine cost limits when using simple greedy methods for dynamically connecting network points as demands arrive gradually.
- •For online service operators: Assess the efficiency gap between easy-to-run greedy algorithms and the best possible solutions for connecting user requests in real time.
A theory result. No direct application yet.
Authors
Iman Gholami, Ilya Hajiaghayi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade
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(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 $Θ(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.