Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-f Time Barrier
share
The dynamic set cover problem has been subject to extensive research since the pioneering works of [Bhattacharya et al, 2015] and [Gupta et al, 2017]. The input is a set system (U, S) on a fixed collection S of sets and a dynamic universe of elements, where each element appears in a most f sets and the cost of each set lies in the range [1/C, 1], and the goal is to efficiently maintain an approximately-minimum set cover under insertions and deletions of elements. Most previous work considers the low-frequency regime, namely f = O(log n), and this line of work has culminated with a deterministic (1+ϵ)f-approximation algorithm with amortized update time O(f^2/ϵ^3 + f/ϵ^2log C) [Bhattacharya et al, 2021]. In the high-frequency regime of f = Ω(log n), an O(log n)-approximation algorithm with amortized update time O(flog n) was given by [Gupta et al, 2017]. Interestingly, at the intersection of the two regimes, i.e., f = Θ(log n), the state-of-the-art results coincide: approximation Θ(f) = Θ(log n) with amortized update time O(f^2) = O(f log n) = O(log^2 n). Up to this date, no previous work achieved update time of o(f^2). In this paper we break the Ω(f^2) update time barrier via the following results: (1) (1+ϵ)f-approximation can be maintained in O(f/ϵ^3log^*f + f/ϵ^3log C) = O_ϵ,C(f log^* f) expected amortized update time; our algorithm works against an adaptive adversary. (2) (1+ϵ)f-approximation can be maintained deterministically in O(1/ϵflog f + f/ϵ^3 + flog C/ϵ^2) = O_ϵ,C(f log f) amortized update time.
READ FULL TEXT