Minimize the number of elements to complete the maximum amount of sets.

87 Views Asked by At

Consider a set of distinct elements $\{a_1, a_2, a_3,\dots, a_n\}$ (the universe) and a collection of sets $S= \{ S_1, S_2, S_3,\dots, S_m \} $ with each set formed out of any strictly positive number of elements.

For a given number $k$ with $0<k < n$, find the $k$ elements that maximize the number of covered sets.

This problem is similar but not identical to the set cover problem and maximum coverage problem.

How is this problem called and which algorithm should be used to solve it?

1

There are 1 best solutions below

0
On

For $1 \leq i \leq n$, let $B_i = \{S_j: S_j \in S, x_i \in S_j\}$. Then apply the maximum coverage problem to the sets $B_i$.