# Covering maximal number of sets using fixed number of elements

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.

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.
• 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. – Gilad Deutsch Apr 1 at 18:36