1
$\begingroup$

Context: I have $m$ groups of a random number of $n$ types. Each type can occur only once for each group. I hope to reduce the groups to the smallest set such that each type occurs at least once.

Problem: Suppose I have an $n * m$ binary matrix which represents the groups of each type.

$$ \begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \end{matrix} $$

Question: Is there an elegant way to determine the smallest subset of rows such that each column sums to at least $1$.

In this example rows 1, 3 and 4 fulfill this.

$$ \begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \end{matrix} $$

I am a biological scientist, so it may be obvious that this is not possible. My Google and Stack Exchange searches did not reveal a method.

$\endgroup$
2
$\begingroup$

This is a set covering problem, which you can solve via integer linear programming as follows. Let $a_{i,j}$ be the $(i,j)$ entry of your matrix. Let binary decision variable $x_i$ indicate whether you select row $i$. The problem is to minimize $\sum_{i=1}^n x_i$ subject to linear constraints: $$\sum_{i=1}^n a_{i,j} x_i \ge 1$$ for each $j\in\{1,\dots,m\}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ In addition, a practical solution to set cover problem is greedy algorithm $\endgroup$ – Vasily Mitch Mar 31 at 21:26
  • $\begingroup$ Thanks so much, I just didn't have the vocabulary to ask my question. $\endgroup$ – Ian Campbell Mar 31 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.