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.


This is the set cover 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}$.

| cite | improve this answer | |
  • $\begingroup$ @Dave: Why did you accept the suggested edit which removed the phrase “If I understand correctly”? $\endgroup$ – Tsuyoshi Ito Apr 14 '11 at 11:43

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.