Stronger adversaries grow cheaper forests: online node-weighted Steiner problems

Sander Borst, Marek Eliáš, 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 b…