# Covering problem

$LaTeX: \min \{c^Tx: Ax \ge 1, \; x \in \{0,1\}^n\}$,
where $LaTeX: x_j=1$ if element $LaTeX: j$ is selected; else, $LaTeX: x_j=0$. The matrix $LaTeX: A$ has 0's and 1's, where the $LaTeX: i$-th row corresponds to the $LaTeX: i$-th set to be covered: $LaTeX: A_{i, j}=1$ means element $LaTeX: j$ is in set $LaTeX: i$; else, $LaTeX: A_{i, j}=0$. The constraint $LaTeX: Ax \ge 1$ means that at least one element of each set must be selected. This could be extended to require $LaTeX: b_i$ elements of set $LaTeX: i$ be selected by writing $LaTeX: Ax \ge b$. Also see vertex cover.