Dynamic Set Cover: Improved Algorithms & Lower Bounds

Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni +2

We give new upper and lower bounds for the {\em dynamic} set cover problem. First, we give a $(1+\epsilon )f$-approximation for fully dynamic set cover in $O(f^2\log n/{\epsilon }^5)$ (amortized)…