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 + ϵ), for any constant ϵ > 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(∆ 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 achieve fast update times together with an approximation that exceeds the static f -approximation by a factor of (at most) 1 + ϵ, for any ϵ > 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 + ϵ) ln n for any ϵ > 0, while achieving the same update time (ignoring dependencies on ϵ) of the best previous algorithms (with approximation significantly larger than ln n). Moreover, we prove that the same algorithms achieve O(minlog 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].