A problem related to maximum the number of bit-1 in binary numbers
WU Chehai
My problem is: I have N binary numbers and each number has L bits. I
want choose M numbers from the N numbers(M < N), so that the bitwise
OR result of the M numbers has the maximum number of bit-1.
For example, I have three binary numbers: 010, 001, 101 and I want to
choose two of them. Obviously, I should choose 010 and 101, becase 010
bitwise OR 101 is 111 which has three bit-1's and other pairs, such as
010 and 001, 001 and 101, can only generate two bit-1s by bitwise OR.
Is this problem NP-hard?
Alan Johnson
Hint: Consider a 3SAT problem with L clauses, each clause corresponding
to a bit position in 3 L-bit numbers. If you solved the above problem
with 3 such numbers, what would it tell you if you got 111 as the
result? What if you got something other than 111?
Alan
WU Chehai
I can have a bool variable e(i) for the ith binary number: e(i)=1 means
the ith number is chosen and e(i)=0 means otherwise. So, every bit
position can be expressed by a clause which has at most i variables.
MAX-SAT is very similar to this problem, but MAX-SAT does not restrict
the number of true bool variables. In my case the number of ture
variables (how many e(i) is true, 1<= i <= N) must be M.
I am wondering whether I can get a reduction from MAX-SAT. I have been
working on this problem for weeks, I still get nothing now.
Am I on the right way? Maybe this problem is in P?
subbu
WU Chehai
I think your idea works!
The binary numbers can be viewed as sets.
My problem is to find at most M sets to cover as many elements(bit-1)
as possible.
If I assume the OR result of all the binary numbers is all bit-1's, my
problem is SET-COVER.
David
>Is this problem NP-hard?
Are you concerned with the complexity with respect to L or not?
WU Chehai
David
>I am concerned with N and M. L can be a constant.
Surely in that case it's polynomial, since M is at most L.
Just examine the O(N^M) possible combinations of M numbers to
find a set whose OR has the maximal number of bits set.
I suspect there are much more efficient algorithms.
WU Chehai
M should be less than N.
So, we have C(N,M) possible combinations. This is not polynomial.
David
As I said, M is at most L, which is a constant, so it is polynomial.
Consider some solution: a set of numbers whose OR has at most L 1's.
Each number must contribute at least 1 distinct 1 bit, or it is
redundant and can be removed without affecting the maximality of
the solution. So M need never be greater than L.
Of course if you insist on exactly M numbers in a solution rather
than at most M numbers, and M > L, you can add any numbers you like
to a solution just to pad it out, but these can be chosen arbitrarily.
To find a solution you need consider only O(N^L) combinations.
WU Chehai
L should be taken into consideration when we analyze the complexity
My problem is in fact the same as MAXIMUM COVERAGE
PROBLEM(http://www.ensta.fr/~diam/ro/online/viggo_wwwcompendium/node146.html),
which is known to be NP-Hard. So I think the problem is NP-Hard.