# Selection over combinatorics that satisfies a distribution

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}

....

1. { 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.

• By "each set contains integers from 1 to N" do you mean "each set contains integers in range 1...N"? – BearAqua Feb 8 '20 at 23:40
• Exactly it's what I meant and I modified the question as you said. Sorry for poor English – Mehmet Doğan Feb 9 '20 at 0:08
• And by selection you mean "take the union of"? – BearAqua Feb 9 '20 at 0:21
• Any criteria about how far from a solution should be from exactly the proposed distribution? In other words, what exactly do you mean by "approximately"? – Rick Decker Feb 9 '20 at 2:21
• I mean that you select at least 1000 sets(L) over these M sets(10000). Why do you "take the union of" them? If you take the union of selected sets you get one single set that all elements occur? @RickDecker I thought your question in the time of asking this question but we can't know about it. Assume that any of M sets do not include "2" but your distribution table says "2" must occur in %10 of 1000 sets. It is not possible as you see. – Mehmet Doğan Feb 9 '20 at 7:11

## 1 Answer

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.