1
$\begingroup$

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.

$\endgroup$

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.