Given a set of elements $N$, a set $S$ of subsets of $N$, and a function $v:S \to \mathbb R$, determine a set $R\subseteq S$ of non-overlapping subsets that maximizes the total value.

Has this problem already been studied somewhere, or is it linked to some well-known optimization problem?

  • 1
    $\begingroup$ Is the function $v$ positive valued? $\endgroup$ – fade2black Jul 20 '17 at 21:48
  • $\begingroup$ No, it is not positive valued. $\endgroup$ – Filippo Bistaffa Jul 21 '17 at 6:25

Yes this problem has already been studied. It is a well-known $NP$-complete problem known as Set-Packing. Your problem is a weighted optimization variation, but the same principles apply.

  • $\begingroup$ I see. Basically set packing is a special case of this problem, with $v(\cdot)=1$ for all subsets. $\endgroup$ – Filippo Bistaffa Jul 21 '17 at 6:31

You can reduce it to the following graph theoretic problem, but I don't know if it is in $P$.

Denote each set in $S$ as a vertex and give it a weight $f(S)$, in other words your vertices are weighted. Then if two sets are overlapping connect them by and edge. Then you have to find a subset $V'$ of vertices such that if $v,u \in V'$ then $(u,v) \notin E$, that is they are not adjacent to each other and sum of weights of vertices in $V'$ have to be maximal.

UPDATE: According to ryan's post it is NP-complete.


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.