Covering maximal number of sets using fixed number of elements

Question

I've encountered some problem which seems general enough to have already been solved.

There is a set of objects $O=\{o_1, o_2,\dots,o_k\}$ and a family of sets $A_1,A_2,\dots,A_t \subseteq O$.

For every 1ドル \leq j < k$ we need to find a subset $O' \subset O$ of size $j$ maximizing the number of sets $A_i$ contained in it.

What is the best algorithm to solve this? I've been thinking about reducing it to a problem in graphs or flow networks but still haven't arrived at a solution.

• Matt Groff: Possibly Related: From "covering designs", and assuming we can pick the sets, we arrive at Steiner systems in the best case. You can see Dan Gordon's page if this is what you're after here: dmgordon.org/cover

Answer 1

Your problem is essentially Minimum $k$-Union. In this problem (switching from $k$ to $\ell$), you want to find $\ell$ sets out of $A_1,\ldots,A_t$ which together cover the least number of elements. Denoting by $f(\ell)$ the solution of this problem and by $g(j)$ the solution of your problem, we have $$ f(\ell) \leq j \Longleftrightarrow \ell \leq g(j). $$ In other words, $g(j)$ is the maximal $\ell$ such that $f(\ell) \leq j$.

Unfortunately, Minimum $k$-Union is NP-hard. You can find some links in this question on StackOverflow.

• Gilad Deutsch: Thanks for the reply. I see the similarity, the problem is I want to find the solution for every 1ドル \leq j < k$. I'd like to use an approximated solution to the minimum k-union, but to solve for every j I'd need to apply the solution for $ 1,2,...,numof matches=M $. since $M$ can be as large as 2ドル^k$ that's not very good. If the processing time of the solution is $T$ then a total time of 2ドル^k * T$ will be needed, whereas if there is a solution which its input is the number of objects from $O$ and which takes time $R,ドル a total time of $k*R$ is needed, assuming $T \approx R$ this is better.