A Lossless Deamortization for Dynamic Greedy Set Cover

The dynamic set cover problem has been subject to growing research attention in recent years. In this problem, we are given as input a dynamic universe of at most <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> elements and a fixed collection of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m$</tex> sets, where each element appears in a most <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex> sets and the cost of each set is in [1/C, 1], and the goal is to efficiently maintain an approximate minimum set cover under element updates. Two algorithms that dynamize the classic greedy algorithm are known, providing <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\log n)$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$((1+\epsilon)\ln n)$</tex>-approximation with amortized update times <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(f \log n)$</tex> and, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\frac{f \log n}{\epsilon})$</tex>, respectively [GKKP (STOC'17); SU (STOC'23)]. The question of whether one can get approximation <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\log n)$</tex> (or even worse) with low worst-case update time has remained open — only the naive <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(f\cdot n)$</tex> time bound is known, even for unweighted instances. In this work we devise the first amortized greedy algorithm that is amenable to an efficient deamortization, and also develop a lossless deamortization approach suitable for the set cover problem, the combination of which yields a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$((1+\epsilon)\ln n){-}$</tex> approximation algorithm with a worst-case update time of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\frac{f \log n}{\epsilon^{2}})$</tex>. Our worst-case time bound — the first to break the naive <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(f\cdot n)$</tex> bound — matches the previous best amortized bound, and actually improves its <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\epsilon$</tex> -dependence. Further, to demonstrate the applicability of our deamortization approach, we employ it, in conjunction with the primal-dual amortized algorithm of [BHN (FOCS'19)], to obtain a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$((1+\epsilon)f)$</tex>-approximation algorithm with a worst-case update time of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\frac{f \log n}{\epsilon^{2}})$</tex>, improving over the previous best bound of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\frac{f \cdot \log ^{2}(C n)}{-3})\ [$</tex> BHNW (SODA'21)]. Finally, as direct implications of our results for set cover, we (i) achieve the first nontrivial worst-case update time for the dominating set problem, and (ii) improve the state-of-the-art worst-case update time for the vertex cover problem.