SODA Conference 2025 Conference Paper
Stronger adversaries grow cheaper forests: online node-weighted Steiner problems
- Sander Borst
- Marek Eliás 0001
- Moritz Venzin
We propose a O (log k log n )-competitive randomized algorithm for online node-weighted Steiner forest. This is essentially optimal and significantly improves over the previous bound of O (log 2 k log n ) by Hajiaghayi et al. [2017]. In fact, our result extends to the more general prize-collecting setting, improving over previous works by a poly-logarithmic factor. Our key technical contribution is a randomized online algorithm for set cover and non-metric facility location in a new adversarial model which we call semi-adaptive adversaries. As a by-product of our techniques, we obtain the first deterministic O (log | C | log | F |)-competitive algorithm for non-metric facility location.