We study the rent-or-buy variant of the online Steiner forest problem on node- and edge-weighted graphs. For n-node graphs with at most ̄n nodes of non-zero weight, and at most k̃ different arriving terminal pairs, we obtain the following: - A deterministic, O (log n log ̄n) -competitive algorithm against adaptive adversaries. This improves on the previous best, O (log⁴ n) -competitive algorithm obtained by the black-box reduction from Yair Bartal et al. , 2001 combined with the previously best deterministic algorithms for the simpler "buy-only" setting. - A deterministic, O (̄nlog k̃) -competitive algorithm against adaptive adversaries. This generalizes the O (log k̃) -competitive algorithm for the purely edge-weighted setting from Seeun Umboh, 2015. - A randomized, O (log k̃ log ̄n) -competitive algorithm against oblivious adversaries. All previous approaches were based on the randomized, black-box reduction from Awerbuch et al. , 2004 that achieves a O (log k̃ log n) -competitive ratio when combined with an algorithm for the "buy-only" setting. Our key technical ingredient is a novel charging scheme to an instance of online prize-collecting set cover. This allows us to extend the witness-technique of Seeun Umboh, 2015 to the node-weighted setting and obtain refined guarantees with respect to ̄n, already in the much simpler "buy-only" setting.
Borst et al. (Thu,) studied this question.