Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating Set

The minimum set cover (MSC) problem admits two classic algorithms: a greedy ln n-approximation and a primal-dual f-approximation, where n is the universe size and f is the maximum frequency of an element. Both algorithms are simple and efficient, and remarkably - one cannot improve these approximations under hardness results by more than a factor of (1 + epsilon), for any constant epsilon > 0. In their pioneering work, Gupta et al. [STOC'17] showed that the greedy algorithm can be dynamized to achieve O(log n)-approximation with update time O(f log n). Building on this result, Hjuler et al. [STACS'18] dynamized the greedy minimum dominating set (MDS) algorithm, achieving a similar approximation with update time O(Delta log n) (the analog of O(f log n)), albeit for unweighted instances. The approximations of both algorithms, which are the state-of-the-art, exceed the static ln n-approximation by a rather large constant factor. In sharp contrast, the current best dynamic primal-dual MSC algorithms, by Bhattacharya et al. [SODA'21] and Assadi-Solomon [ESA'21], both with update time O(f(2)) - exceed the static f-approximation by a factor of (at most) 1 + epsilon, for any epsilon > 0. This paper aims to bridge the gap between the best approximation factor of the dynamic greedy MSC and MDS algorithms and the static ln n bound. We present dynamic algorithms for weighted greedy MSC and MDS with approximation (1+epsilon) ln n for any epsilon > 0, while achieving the same update time (ignoring dependencies on epsilon) of the best previous algorithms (with approximation significantly larger than ln n). Moreover, we prove that the same algorithms achieve O(min{log n, log C}) amortized recourse; the recourse measures the number of changes to the maintained structure per update step, and the cost of each set lies in the range [1/C, 1].