Dynamic Set Cover: Improved Amortized and Worst-Case Update Time

内容摘要

In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal $\min(O(\log n), f)$ approximation factor. (Throughout, $m$, $n$, $f$, and $C$ are parameters denoting the maximum number of sets, number of elements, frequency, and the cost range.) In the high-frequency range, when $f=Ω(\log n)$, this was achieved by a deterministic $O(\log n)$-approximation algorithm with $O(f \log n)$ amortized update time [Gupta et al. STOC'17]. In the low-frequency range, the line of work by Gupta et al. [STOC'17], Abboud et al. [STOC'19], and Bhattacharya et al. [ICALP'15, IPCO'17, FOCS'19] led to a deterministic $(1+ε)f$-approximation algorithm with $O(f \log (Cn)/ε^2)$ amortized update time. In this paper we improve the latter update time and provide the first bounds that subsume (and sometimes improve) the state-of-the-art dynamic vertex cover algorithms. We obtain: 1. $(1+ε)f$-approximation ratio in $O(f\log^2 (Cn)/ε^3)$ worst-case update time: No non-trivial worst-case update time was previously known for dynamic set cover. Our bound subsumes and improves by a logarithmic factor the $O(\log^3 n/\text{poly}(ε))$ worst-case update t