Fully Dynamic Set Cover -- Improved and Simple
share
In this paper, we revisit the unweighted set cover problem in the fully dynamic setting. In contrast to the offline setting where a static set of n elements need to be covered using minimum number of sets from a family F, here elements to be covered change over time and can be inserted and deleted. The goal is to maintain a close to optimal set cover solution at every time step while minimizing the update time. In the offline setting, several textbook algorithms exist from early eighties that give a factor f approximation algorithm for set cover where f is the maximum frequency of an element. Whereas, in the dynamic setting, even today, there does not exist a factor O(f)-approximation algorithm for set cover, except for when f=2 (the special case of unweighted vertex cover). The best approximation bound known for dynamic set cover is O(f^2) [Bhattacharya et al. ICALP 2015] with an amortized update time of O(fn). Subsequent works get an O(f^2) amortized update time but with a worse approximation factor of O(f^3) [Gupta et al., STOC 2017; Bhattacharya et al., IPCO 2017]. In this paper, we give the first f(1+ϵ)-approximation algorithm for the fully dynamic unweighted set cover problem for any ϵ >0. An important contribution of this work lies in its conceptual simplicity. First, we take one of the simplest possible deterministic algorithms for the offline set cover and show that it achieves a factor f(1+ϵ)-approximation in O(f/ϵ) expected amortized time when deletions are randomly ordered. Next to handle any sequence of updates, we transfer the randomness to the algorithm instead. This recipe of switching the role of randomness turns out to be extremely useful. We get the first f(1+ϵ)-approximation in O(fn/ϵ) amortized update time on expectation and with high probability.
READ FULL TEXT