2
$\begingroup$

I have a question that might belong better on the CS SE; let me know and I will move it. This comes from a research project and is a reframing of our question. Essentially, we have some matrix that is $m \times n$, where $m > n$. These matrices are generally diagonal and are only $1$s and $0$s. An example is: $$ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} $$

We want to find the minimum amount of columns such that each row has at least one $1$ in it. For example, there are three possible "correct" answers to this:
cols 1, 2, 4, 5
cols 1, 2, 3, 5
cols 1, 3, 4, 5

While it would be great to have the specific combination of columns, it would also suffice to have simply the minimum number of columns. I think there should be an easier way to do this than brute-forcing. That's what I've been doing so far via Jupyter and as you can imagine, the complexity gets bad fast. So, is there a way to define this problem in terms of linear independence? Is there a linear algebra trick that might make this problem much simpler? Is this an integer linear programming thing? Is this a well-known problem in anyone's field? I appreciate any insight.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

This looks like the set cover problem. We look for a covering of $S:=\{1,\ldots,m\}$ by sets $S_j:=\{i: a_{ij}=1\}$, where $A=(a_{ij})$ is the given binary matrix. Since the problem is NP-hard, there is no linear algebra trick to provide the minimal solution apart from the brute force approach.

There are methods, however, which provide an approximate solution for the problem. For example, a greedy algorithm suggests itself: starting with an empty cover, build iteratively the cover by selecting iteratively at step $k$ a subset $S_{i_k}$ which covers the maximum of uncovered elements. This can lead to suboptimal solutions but is quite easy to implement.

$\endgroup$
1
  • $\begingroup$ That is essentially what we are trying to do but in a poset context. I've been able to implement generally-ok greedy algorithms for some simpler structures (Boolean lattices for example) but have been unable to do effectively so for posets that lack that symmetry and consistency. I was hoping the reframing would be not an NP-hard problem, but makes sense lol $\endgroup$ Apr 9 at 18:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .