The online Steiner forest problem is a classical problem in the field of online algorithms. For a long time, we have had an optimal algorithm for this problem, but only in the edge-weighted setting. The node-weighted setting is fundamentally more challenging. We finally propose an algorithm for node-weighted Steiner forest that is essentially optimal. A key ingredient for proving this result is a new adversarial model, called semi-adaptive adversaries.

This work will appear in SODA'25.