Entropy and set covering (Q1092816): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:10, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Entropy and set covering |
scientific article |
Statements
Entropy and set covering (English)
0 references
1985
0 references
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.
0 references
set representation
0 references
least-cost set covering
0 references
minimum covering
0 references
maximum joint probability problem
0 references
weighted cross entropy
0 references