Dynamic set cover: improved algorithms and lower bounds
Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha · 2019
We give new upper and lower bounds for the dynamic set cover problem. First, we give a (1+є) f-approximation for fully dynamic set cover in O(f2logn/є5) (amortized) update time, for any є > 0, where f is the maximum number of sets that an element belongs to. In the decremental setting, the update time can be improved to O(f2/є5), while still obtaining an (1+є) f-approximation. These are the first algorithms that obtain an approximation factor linear in f for dynamic set cover, thereby almost matching the best bounds known in the offline setting and improving upon the previous best approximation of O(f2) in the dynamic setting.