Restricted Parameter Range Promise Set Cover Problems Are Easy

Hao Chen

Let $(\mathbf{U},\mathbf{S},d)$ be an instance of Set Cover Problem, where $\mathbf{U}=\{u_1,...,u_n\}$ is a $n$ element ground set, $\mathbf{S}=\{S_1,...,S_m\}$ is a set of $m$ subsets of ${\…