Dynamic ((1+π) ln π)-Approximation Algorithms for Minimum Set Cover and Dominating Set
Shay Solomon, Amitai Uzrad Β· 2023
The minimum set cover (MSC) problem admits two classic algorithms: a greedy lnn-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.