1
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gilad Deutsch Apr 1 at 18:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.