2
$\begingroup$

Suppose I have the following set of bit sets:

 [1,]    0    1    1    1    0    1    0    1    0     0
 [2,]    1    0    1    1    0    0    0    1    0     1
 [3,]    0    0    1    0    1    1    0    1    1     0
 [4,]    1    0    1    0    0    0    0    1    1     1
 [5,]    0    1    0    1    0    1    0    1    1     0
 [6,]    0    1    1    1    1    0    0    1    0     0
 [7,]    1    1    0    0    0    1    1    0    0     1
 [8,]    1    1    0    1    1    1    0    0    0     0
 [9,]    0    1    1    0    1    1    0    0    0     1
[10,]    0    1    1    1    0    0    1    1    0     0

How would I go about finding the largest set such that the bitwise-or of that set does not exceed n bits in the "on" position.

For example, if I or rows 1 & 10...

 [1,]         0    1    1    1    0    1    0    1    0     0
[10,]         0    1    1    1    0    0    1    1    0     0
[1 or 10,]    0    1    1    1    0    1    1    1    0     0

This gives me 7 bits in the "on" position.

Now suppose my limit was 8 bits... how would I go about finding the largest set?

Edit: I know how to do this as a mixed-integer-linear program, but I'm assuming there's a nifty graph approach.

$\endgroup$
1
$\begingroup$

This problem is NP-hard. It is called "the minimum-k-union problem". Given a universe $U$ and a family of sets $\mathcal{F}$ over this universe. Are there $k$ distinct sets in $F$ such that the union of all these sets has size at most $d$.

Your presentation is the matrix formulation of this problem where each column corresponds to an element in the universe and each row corresponds to a set in the family. We are looking for $k$ rows such that the number of columns having at least one "1" is at most $d$.

The Problem is NP-hard and has approximation algorithms. Here is a link for one of them.

$\endgroup$

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.