0
$\begingroup$

I want to know if a specific version (and what´s its name?) of the Set Partitioning Problem is NP-Complete, and if, is NP-Hard?

Problem:

Given a set of elements $e_i$ where $i={1,...,n}$, each with an associated weight $w(e_i)$, we want to find an optimum partition of these elements into a set of $S_j$ subsets where $j={1,...,k}$. Each subset $S_j$ has an objective weight $W_j$. We define a subset's weight as $w(S_j) = \sum_{{e_i}\in{S_j}} w(e_i)$ where $w(S_j)=0$ if and only if $S_j=\emptyset$. Then the objective is to minimize the sum of the absolute deviation of the weights $w(S_j)$ w.r.t. the objective weights $W_j$:

$$min \sum_{j=1}^{k} |w(S_j) - W_j|$$

I do not really need a proof, just an actual answer and if possible, some reference to a paper or an article about it.

|cite|improve this question
$\endgroup$
  • $\begingroup$ How are the $W_j$'s given? Since there are exponentially many, it is important to specify this. If for example they are given by an efficient program which takes a subset as input and outputs its weight, then the decision version of your problem is NP hard, by a reduction from subset sum. Given a subset sum instance with value $k$ and sum of all elements $s$, set the weight of all subsets whose sum is not $s-k$, $k$ to infinity. $\endgroup$ – Ariel Dec 19 '17 at 6:41
  • 1
    $\begingroup$ @Ariel There are only $k$ many values $W_j$, namely $W_1,\ldots,W_k$. $\endgroup$ – Yuval Filmus Dec 19 '17 at 11:33
  • 1
    $\begingroup$ Your problem is NP-hard by reduction from SUBSET-SUM. $\endgroup$ – Yuval Filmus Dec 19 '17 at 11:34
  • $\begingroup$ @Ariel, suppose the wheight is previously set array.. Thanks for the comments! Do you have a name for the problem? $\endgroup$ – DarK_FirefoX Dec 19 '17 at 15:32

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.