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

Shay Solomon, Amitai Uzrad

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…