Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
To buy or not to buy: deterministic rent-or-buy problems on node-weighted graphs
Sander Borst, Moritz Venzin
We study the rent-or-buy variant of the online Steiner forest problem on node- and edge-weighted graphs. For -node graphs with at most non-zero node-weights, and at mo…
cs.DS2024
Stronger adversaries grow cheaper forests: online node-weighted Steiner problems
Sander Borst, Marek Eliáš, Moritz Venzin
We propose a -competitive randomized algorithm for online node-weighted Steiner forest. This is essentially optimal and significantly improves over the previous b…