Algorithms with improved accuracy estimates for the set covering problem. (Russian) Zbl 1100.90026

Ageev, A. A.

Diskretn. Anal. Issled. Oper., Ser. 2 11, No. 1, 3-10 (2004).

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.

Reviewer: Yu. Kochetov (Novosibirsk)

MSC:

90C10	Integer programming
90C27	Combinatorial optimization
90C60	Abstract computational complexity for mathematical programming problems

Keywords:

set cover; NP-hard problem