2020/02/25 by Sayan Bhattacharya, Monika Henzinger, Bhattacharya, Sayan +5 · 4 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.2002.11171
openalex publication_date 2020/02/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(flog2 (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(log3 n/poly(ε)) worst-case update time for unweighted dynamic vertex cover (i.e., when f=2 and C=1) by Bhattacharya et al. [SODA'17]. 2. (1+ε)f-approximation ratio in O((f2/ε3)+(f/ε2) log C) amortized update time: This result improves the previous O(f log (Cn)/ε2) update time bound for most values of f in the low-frequency range, i.e. whenever f=o(log n). It is the first that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [SODA'19] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1).