Entropy and set covering

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09) Integer programming (90C10) Measures of information, entropy (94A17)

Review text

In the paper the least-cost set covering problem \[ LC: \min (c^ Tx\quad | \quad Ax\geq 1,\quad x_ j\in \{0,1\}) \] and its special case, the minimum covering problem \[ MC: \min (1^ Tx\quad | \quad Ax\geq 1,\quad x_ j\in \{0,1\}) \] are dealt with. In the problems above A is the incidence matrix, x is a binary vector to be determined and c is the cost vector for incorrect choices in the covering procedure. It is shown in the paper that the prior probabilities \(p_ j\) for the j'th subset participating in an optimal covering can be uniquely determined from the incidence matrix A. The probabilities are given by the principal row eigenvector of \(A^*A\), where \(a^*_{ji}=1-a_{ij}\). These probabilities can be used to formulate the maximum joint probability problem \[ MP: \min (-\Sigma x_ j \log p_ j\quad | \quad Ax\geq 1,\quad x_ j\in \{0,1\}), \] whose objective function is shown to be equivalent to cross entropy or weighted cross entropy. Further, connections of the set covering problem e.g. with the set representation problem and integer programming are also discussed.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Entropy and set covering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1092816)