1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ By "each set contains integers from 1 to N" do you mean "each set contains integers in range 1...N"? $\endgroup$ Feb 8, 2020 at 23:40
  • $\begingroup$ Exactly it's what I meant and I modified the question as you said. Sorry for poor English $\endgroup$ Feb 9, 2020 at 0:08
  • $\begingroup$ And by selection you mean "take the union of"? $\endgroup$ Feb 9, 2020 at 0:21
  • 1
    $\begingroup$ 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"? $\endgroup$ Feb 9, 2020 at 2:21
  • $\begingroup$ 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. $\endgroup$ Feb 9, 2020 at 7:11

1 Answer 1

3
+25
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.