An Improved Analysis of Greedy for Online Steiner Forest

Étienne Bamas, Marina Drygala, Andreas Maggiori

This paper considers the classic Online Steiner Forest problem where one is given a (weighted) graph $G$ and an arbitrary set of $k$ terminal pairs $\{\{s_1,t_1\},\ldots ,\{s_k,t_k…