Selection over combinatorics that satisfies a distribution

Question

I'm having an exciting problem that I could not manage to find an optimized solution. I actually have no idea if the problem is already known or not.

Here is the problem :

Consider a list of M sets that ( M = 10000 )

• each set contains integers in range 1... N. (Let's say N=50)
• each set has the size of K. ( Let's say K=10)
• each element in the set is distinct.

Sample sets are

1. { 1,2,3,4,5,6,7,8,9,10}
2. { 2,4,5,7,9,11,13,15,20,25}
3. { 4,5,8,12,16,30,41,42,45,49}
4. { 2,6,11,18,24,27,31,36,39,43}

....

10000. { 3,5,8,17,19,23,34,37,38,46 }

You should select L sets(Let's say L=1000) from given 10000 sets. This selection must approximately satisfy a distribution table like below

• 1=> 100 %
• 2=> 80 %
• 3=> 100 %
• 4=> 15 %

...

• 50=> 20%

It means that 1 should occur in all selections, 2 should occur 80% of the selections and goes on ... I will try to solve the problem by trying a random-walk algorithm that exchanges a set in each iteration.

I'm sorry if I did not express my problem well. It would be great if you could share similar problems with mine or could express your approach to the problem.

Answer 1

Consider the following special case where for each element $i$ the table contains the constraint $\#i \geq (1/l) \cdot l$. This means we need to select the sets in such a way that each element appears at least once. This problem is called the set covering problem, where you have to output whether there is a subset of $l$ sets in the input that covers all the elements in the ground-set. It is an NP-complete problem and since it is a special case of your problem, your problem is NP-complete as well (it is clearly in NP since an NTM can guess all possible tuples of $l$ subsets and accept if the union of subsets in any of the guessed tuples covers the ground-set). So You should not expect a polynomial answer.

On the other hand, an exponential trivial solution would be to try packing all sets of $l$ subsets which are at most $n \choose l$ and try for each of them if they satisfy all the constraints in $O(l \cdot r)$ where $r$ is the number of the constraints. This totals in an $O(n^{l+1}r)$. There are a lot of improvements on this running time I think but you should not expect something sub-exponential.