1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

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}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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