Stochastic Gradient Meets Randomized Rounding: New Algorithms for Node-Weighted Steiner Problems
TL;DR
A new $O(\log n)$ approximation algorithm for Node Weighted Steiner Tree and Node Weighted Steiner Forest that matches the bounds of Klein&Ravi, but has the advantage that they work in the online setting when the terminal pairs are revealed in random order.
Abstract
We give a new $O(\log n)$ approximation algorithm for Node Weighted Steiner Tree and Node Weighted Steiner Forest. Our algorithm matches the bounds of Klein&Ravi [J. Algorithms'95] which are best possible unless P = NP, but have the advantage that they work in the online setting when the terminal pairs are revealed in random order. To obtain our results, we combine the LearnOrCover framework due to Gupta, Kehne, Levin [FOCS'21] with the Augmented Greedy algorithm of Berman&Coulston [STOC'97] for online edge-weighted Steiner Forest. Neither algorithm suffices on its own, but the analyses dovetail to imply our guarantee. Run offline, the algorithm reduces to a very simple randomized rounding scheme that (in spirit) reduces Node Weighted Steiner Forest to Edge Weighted Steiner Forest, and we hope this idea finds further applications.