Entropy and set covering (Q1092816)

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.