Quantity coverage problem

The set cover problem (often with set-covering problem listed) is a decision problem of combinatorics .

It asks whether for a set and subsets of and a natural number there is a union of or fewer subsets that corresponds to the set (coverage). ${\displaystyle U}$ ${\displaystyle n}$ ${\displaystyle S_{j}}$ ${\displaystyle U}$ ${\displaystyle k\leq n}$ ${\displaystyle k}$ ${\displaystyle S_{j}}$ ${\displaystyle U}$

Formulated as an optimization problem, a coverage with the smallest possible number of subsets is sought or, if costs are assigned to the subsets , coverage with the lowest possible costs. ${\displaystyle S_{j}}$ ${\displaystyle S_{j}}$ ${\displaystyle c_{j}}$

The set coverage problem belongs to the list of the 21 classical NP-complete problems , of which Richard Karp was able to show that they belong to this class in 1972 .