<p>This is the <a href="http://en.wikipedia.org/wiki/Set_cover_problem" rel="nofollow">set cover</a> problem.</p>

<p>The universe $\mathcal{U}$ corresponds to the rows of the matrix $M$, and each member of $\mathcal{S}$ corresponds to each column. The entry $m_{i,j}$ is true if and only if the $i$-th element of $\mathcal{U}$ belongs to the $j$-th member of $\mathcal{S}$.</p>

CC BY-SA 3.0
2011-04-14T11:43:47.817Z
@Dave: Why did you accept the suggested edit which removed the phrase “If I understand correctly”?
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-14T05:50:45.300Z
2011-04-14T08:18:41.327Z
2011-04-14T08:18:41.327Z
Yoshio Okamoto
<p>I am looking for the best known algorithm for the following problem:
Input: Matrix M with R rows and C cols and values true-false in each position
Output: Minimum number of cols such that the OR operation between all selected cols results in R trues. </p>

<p>I think another form of this problem is: Given C numbers of N bits, get the minimum amount of numbers needed to sum 2^N - 1.</p>

<p>In case this is NP-Complete, then does someone know where can I find the reduction? And is there any pseudo-polynomial algorithm? Maybe using dynamic programming on some bounded variable?</p>

<p>Thanks in advance.</p>

<ds.algorithms>
Best known algorithm for a common problem.
user2582
# Best known algorithm for a common problem.

(Asked by: username_0 on 2011-04-14)

I am looking for the best known algorithm for the following problem:
Input: Matrix M with R rows and C cols and values true-false in each position
Output: Minimum number of cols such that the OR operation between all selected cols results in R trues.

I think another form of this problem is: Given C numbers of N bits, get the minimum amount of numbers needed to sum 2^N - 1.

In case this is NP-Complete, then does someone know where can I find the reduction? And is there any pseudo-polynomial algorithm? Maybe using dynamic programming on some bounded variable?

Thanks in advance.

**Tags:** ds.algorithms

---

## 1 answers

### Answer by username_1 on 2011-04-14. Score: 9 | Accepted answer

This is the [set cover](http://en.wikipedia.org/wiki/Set_cover_problem) problem.

The universe $\mathcal{U}$ corresponds to the rows of the matrix $M$, and each member of $\mathcal{S}$ corresponds to each column. The entry $m\_{i,j}$ is true if and only if the $i$-th element of $\mathcal{U}$ belongs to the $j$-th member of $\mathcal{S}$.

> **Comments:**
> **username_2**: @Dave: Why did you accept the suggested edit which removed the phrase “If I understand correctly”?  

---

