5
$\begingroup$

This problem may have been worked out before but I don't know where to start looking so I hope one of you can help me. The problem is as follows:

There are $N$ variable-sized finite sets $\boldsymbol{X}_i$, $i=1..N$ containing integers. The sets may overlap i.e. an item $x_i \in \boldsymbol{X}_1$ may also occur in another set, i.e. $x_i \in \boldsymbol{X}_2$. There is a measure $m_i = \mathrm{cost}(\boldsymbol{X}_i)$ that can be calculated for each set $\boldsymbol{X}_i$ and for any union of sets, e.g. $\mathrm{cost}(\bigcup\limits_{i=1,2}\boldsymbol{X}_i)$.

How to find the combination of (unions of) sets containing at least once all the items from the original sets $\boldsymbol{X}_i$, such that the sum of the resulting measures $m$ is minimized?

The "brute force" approach would be to generate all possible combinations of unions of sets (do not unite any sets, unite all sets, or unite some sets), calculate the sum of the measures of these combinations and then select the combination yielding the lowest sum of measures. However, I'm sure this can be done more elegantly. Can someone point me in the right direction?

$\endgroup$
5
  • $\begingroup$ The original sets have finite cardinality? $\endgroup$ – user76568 Jan 8 '14 at 15:26
  • $\begingroup$ Yes. I will update the description of the problem accordingly. $\endgroup$ – Wouter Donders Jan 8 '14 at 15:35
  • $\begingroup$ Why not take the union of all the sets? Each item occurs exactly once in this union, so it is an admissible solution, and of course the "measure" of any combination of unions of sets must be at least the measure of the union of all sets, since every element in the union must occur at least once in the combination of sets. I must be misunderstanding the problem... $\endgroup$ – Will Nelson Jan 9 '14 at 10:56
  • $\begingroup$ @WillNelson The "measure" I am talking about is not a measure in the traditional sense. It's a cost function based on the cardinaltiy of the set being considered. This cost is not always lowest when taking the union of all sets. $\endgroup$ – Wouter Donders Jan 9 '14 at 15:41
  • $\begingroup$ I understand the measure is just the cardinality. Here is what I think you want, correct if I'm wrong: choose sets $S_1,\ldots,S_r$ such that each $S_i$ is a union of $X_j$'s and such that $X_i\subset\cup_j S_j$ for all $i=1,\ldots,N$. The objective is to minimize $\sum_i |S_i|$. If that's the problem, then the solution is to choose $r=1$ and $S_1=\cup_i X_i$. $\endgroup$ – Will Nelson Jan 9 '14 at 16:16

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.