1
$\begingroup$

Let's say I have 100 sets of values, and each set contains roughly 100,000 values. From these sets, I want to find the 10 sets that collectively have the largest number of unique values.

The brute force method of just checking all combinations is a combinatorial nightmare. I also thought about doing a rough approach (solution doesn't have to be perfectly optimal) of just finding 'the next best set' to add in sequence. So finding the largest set, then checking each of the rest of the 99 sets for smallest overlap, then checking the next 98 sets for smallest overlap, etc, but that's still 100+99+98+97+96+95+94+93+92+91 = 955 things to do.

Is there something more efficient?

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ Your problem is known as Maximum Cover. It is NP-hard, but has a simple, constant factor approximation algorithm. $\endgroup$
    – Yuval Filmus
    Commented Dec 4, 2019 at 4:04
  • $\begingroup$ Interesting. I looked it up and found the 'Greedy' approximation, which is exactly the approximation I proposed if I understand it correctly, but in my example that still leaves a very large number of coverage checks. Is there something where I can check coverage like 500 times and get a 'good enough' result? $\endgroup$
    – CHP
    Commented Dec 4, 2019 at 10:24
  • $\begingroup$ Or rather, is there a best approach if i only want to check coverage ~500 times? $\endgroup$
    – CHP
    Commented Dec 4, 2019 at 10:31
  • $\begingroup$ The greedy algorithm is much much more efficient than what you wrote. I suggest taking another look at it. $\endgroup$
    – Yuval Filmus
    Commented Dec 4, 2019 at 18:08
  • 1
    $\begingroup$ The running time should be proportional to $100 + 99 + \cdots + 91$ rather than to $100 \cdot 99 \cdots 91$, which is a big difference. $\endgroup$
    – Yuval Filmus
    Commented Dec 4, 2019 at 18:34

1 Answer 1

Reset to default
1
$\begingroup$

Your problem is known as Maximum coverage. The greedy algorithm (repeatedly take a set which covers the maximum number of uncovered elements) is a $1-1/e$ approximation, and runs quite efficiently.

Improve this answer
$\endgroup$

Your Answer

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

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