# zbMATH — the first resource for mathematics

Algorithms with improved accuracy estimates for the set covering problem. (Russian) Zbl 1100.90026
The classical set covering problem is considered: given a finite set $$I$$ and a family of its subsets $$\{S_j\mid i\in J\}$$ with non-negative weights $$w_j$$, find a subfamily $$\{S_j\mid j\in J^*\}$$ with minimal total weight among all families whose union coincides with $$I$$. Algorithms with improved accuracy estimates are proposed for some NP-hard partial cases of the problem.

##### MSC:
 90C10 Integer programming 90C27 Combinatorial optimization 90C60 Abstract computational complexity for mathematical programming problems
##### Keywords:
set cover; NP-hard problem