Minimum Set Cover Optimisation Problem

Definition

Minimum Set Cover Optimisation Problem

Instance: A finite universe $U$ and an indexed family $S_1,\dots ,S_q\subseteq U$.

Feasible solutions: Index sets $J\subseteq \{1,\dots ,q\}$ satisfying ${\bigcup }_{j\in J}{S}_j=U$.

Objective: Minimise $|J|$:
$\mathrm{OPT}=\min \{|J|:{\bigcup }_{j\in J}{S}_j=U\}.$
A solution selects a set cover of minimum cardinality, not merely one from which no set can be removed. If ${\bigcup }_j{S}_j\ne U$, the instance is infeasible; if $U=\varnothing$, the empty selection is optimal.