I'm looking for work done on solving some problem which is very similar to the minimum k-union.

The problem:

There's a set of elements $E=\{e_1,e_2,...,e_k\}$ of size $k$, and a family of sets $S_1,S_2,...,S_t$ where each set $S_i$ is contained in $E$: $S_i \subseteq E$.

The objective is to find for each $1 \leq j\leq k$ the "best" subset of $E$ of size $j$, where "best" means that it has the biggest number of sets $S_i$ which are contained in it. The problem, as well as it being NP-hard, is described here too.

I could use solutions to the minimum k-union to solve this, but that wouldn't be ideal regarding computation time, so hopefully this problem can be reduced to some problem that has approximation algorithms to it.


Your Answer

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

Browse other questions tagged or ask your own question.