Covering problem

From Glossary

Jump to: navigation, search

The idea is to select enough members in each of a specified collection of sets; that defines covering the sets. Subject to this, there is a cost for the elements selected, and the objective is to minimize total cost. The IP form of the usual set covering problem is

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.

Personal tools