# Is a minimal deviation version of set partition problem NP-Hard?

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.

• 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. – Ariel Dec 19 '17 at 6:41
• @Ariel There are only $k$ many values $W_j$, namely $W_1,\ldots,W_k$. – Yuval Filmus Dec 19 '17 at 11:33
• Your problem is NP-hard by reduction from SUBSET-SUM. – Yuval Filmus Dec 19 '17 at 11:34
• @Ariel, suppose the wheight is previously set array.. Thanks for the comments! Do you have a name for the problem? – DarK_FirefoX Dec 19 '17 at 15:32