An Improved Algorithm for Dynamic Set Cover
share
We consider the minimum set cover problem in a dynamic setting. Here, we are given a universe of elements U and a collection of sets S⊆ 2^U as input, where each set s ∈S has a cost 1/C < c_s < 1 for some parameter C > 1. The input keeps changing via a sequence of updates. Each update inserts/deletes an element in the universe, and specifies the sets in containing that element. The goal is to maintain a set cover of (approximately) minimum cost with as small update time as possible. Let n denote the number of sets in S, and let m and f respectively denote the maximum number of elements in the universe and the maximum frequency of an element across all the updates. This problem has received significant attention in recent years in the dynamic algorithms community. Gupta et al. [STOC `17] designed a deterministic Θ(log m)-approximation algorithm for this problem that has an update time of O(f log m). On the other hand, the line of work by Bhattacharya et al. [ICALP `15], Bhattacharya et al. [IPCO `17], Gupta et al. [STOC `17], Abboud et al. [STOC `19] and Bhattacharya et al. [FOCS `19] very recently led to a deterministic (1+ϵ)f-approximation algorithm with O(f log (Cm)/ϵ^2) update time. In this paper, we obtain the first dynamic algorithm for this problem with near-optimal approximation ratio whose update time is independent of m, n. Specifically, our algorithm is deterministic and it achieves an approximation ratio of (1+ϵ)f and an update time of O((f^2/ϵ^3)+(f/ϵ^2) log C). Our algorithm is based on the dynamic primal-dual framework, and it carefully combines the ideas from the dynamic vertex cover algorithm of Bhattacharya and Kulkarni [SODA `19] and the dynamic set cover algorithm of Bhattacharya et al. [FOCS `19].
READ FULL TEXT