Can this be solved in polynomial time?
- From: Leo2157@xxxxxxxxx
- Date: 13 Apr 2007 15:32:22 -0700
I have M bit-strings with N bits each. I need to find K strings, so
that logical OR of all the chosen strings has the most bits set.
Or in other words:
You have a set S of size N.
You are given M subsets of S.
Find K of the given subsets, so that their union is of maximal size.
Can this problem be solved efficiently? If so, how?
Thanks
.
- Follow-Ups:
- Re: Can this be solved in polynomial time?
- From: David Wagner
- Re: Can this be solved in polynomial time?
- Prev by Date: Two-step Non-deterministic Process for Solving NP Problems
- Next by Date: Re: Can this be solved in polynomial time?
- Previous by thread: Two-step Non-deterministic Process for Solving NP Problems
- Next by thread: Re: Can this be solved in polynomial time?
- Index(es):