Dynamic set cover: improved algorithms and lower bounds

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 ( f 2 log n /є 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 ( f 2 /є 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 ( f 2 ) in the dynamic setting. To complement our upper bounds, we also show that a linear dependence of the update time on f is necessary unless we can tolerate much worse approximation factors. Using the recent distributed PCP-framework, we show that any dynamic set cover algorithm that has an amortized update time of O ( f 1−є ) must have an approximation factor that is Ω( n δ ) for some constant δ>0 under the Strong Exponential Time Hypothesis.

Authors

• Amir Abboud
• Raghavendra Addanki
• Fabrizio Grandoni 0001
• Debmalya Panigrahi
• Barna Saha

Keywords

• competitive ratio
• dynamic algorithm
• online algorithm
• randomized algorithm
• set cover