REU Project

The online Steiner forest problem asks an algorithm to connect demand pairs arriving sequentially in a weighted undirected graph, without knowledge of future demands and without deleting previously purchased edges. Whereas the offline problem has constant-factor approximations, the optimal ratio in the fully online setting is O(log k) for k demands. We study Steiner forest in the online algorithms with a sample framework, which interpolates between these settings by revealing each demand independently with probability p before the online phase. Previous work by Argue et al. 2022 gives an O(log 1/p) ratio for Steiner tree. We developed an O(1/p)-competitive algorithm for Steiner forest, giving a guarantee independent of the total number of demands.