Stochastic Gradient Meets Randomized Rounding: New Algorithms for Node-Weighted Steiner Problems

Joseph Koutsoutis, Jesse Lerner, Roie Levin +1

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 '…