×

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
PDF BibTeX XML Cite