I have a collection $S$ of sets $S_i$. Each $S_i$ has a weight given by how many times this set was observed in some data. I now want to find the $k$ elements that maximize the cumulative weight of all sets that can be covered by those elements (that is, those sets that contain only elements from those $k$ selected).

As an example, let $S$ consist of the following sets and corresponding weights: $$ \{1\} = 20 \\ \{2\} = 10 \\ \{3\} = 5 \\ \{1,2\} = 10 \\ \{2,3\} = 40 \\ \{1,3\} = 5 \\ \{1,2,3\} = 5\\ $$

In this case, I want my solution for $k = 2$ to be $\{2,3\}$, as $\{1,2\}$ has a cumulative weight of $20+10+10=40$, $\{1,3\}$ has a cumulative weight of $20+5+5=30$ and $\{2,3\}$ has a cumulative weight of $10+5+40=55$.

I have the feeling that my problem resembles a maximum coverage problem, but with a limit on the elements, not the sets, and with the sets having weights instead of the elements.

  • $\begingroup$ See if this helps: math.stackexchange.com/questions/2136561/…. $\endgroup$ – Yuval Filmus Jun 26 at 16:52
  • $\begingroup$ This minimum k-union problem seems to go in the right direction, but it tries to find $k$ of $n$ sets such that the number of elements in their union is minimal, while I try to find $k$ elements such that sum of weights for all of the original $n$ sets which are covered by those elements is maximal. $\endgroup$ – aWdas Jun 26 at 20:44
  • $\begingroup$ Perhaps you can relate the two problems. $\endgroup$ – Yuval Filmus Jun 26 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.