# For a collection $S$ of weighted sets $S_i$, find those $k$ elements that maximise the sum of weights of all sets $S_i$ covered by them

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.

• See if this helps: math.stackexchange.com/questions/2136561/…. – Yuval Filmus Jun 26 at 16:52
• 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. – aWdas Jun 26 at 20:44
• Perhaps you can relate the two problems. – Yuval Filmus Jun 26 at 21:18