2026-07-23T21:24:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25505 2026-03-19T13:34:17Z ddc:004 open_access

To Buy or Not to Buy: Online Rent-Or-Buy on Node-Weighted Graphs Borst, Sander Venzin, Moritz online network design node-weighted Steiner forest derandomization 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(̄{n}log 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sander Borst and Moritz Venzin 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.16 urn:nbn:de:0030-drops-255054 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.16 eng https://creativecommons.org/licenses/by/4.0/legalcode