Hi,ALL 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.
WU Chehai wrote: > Hi,ALL > 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?
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?
Thanks, Alan 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?
Thanks very much, subbu 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.
In <1145179300.551483.76...@e56g2000cwe.googlegroups.com> "WU Chehai" <wuche...@gmail.com> writes:
>Hi,ALL >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?
Are you concerned with the complexity with respect to L or not?
In <1145341516.922947.164...@i40g2000cwc.googlegroups.com> "WU Chehai" <wuche...@gmail.com> writes:
>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.
In <1145353036.079482.110...@j33g2000cwa.googlegroups.com> "WU Chehai" <wuche...@gmail.com> writes:
> M has little to do with L. > M should be less than N. > So, we have C(N,M) possible combinations. This is not polynomial.
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.
