0
$\begingroup$

The problem is: split the given array with $L$ elements, $A$, into $K$ subsets such that maximum sum of all subsets is minimum. I have known that the problem that partitioning the multiset $S$ into two subsets $S_1$, $S_2$ such that the difference between the sum of elements in $S_1$ and the sum of elements in $S_2$ is minimized is NP-hard. It seems that the aforementioned problem is harder that the known NP-hard problem.
Could anyone explain why my questioned problem is NP-hard? It will be very appreciated that you could offer some formal references or paper.
FYI: I have read this post, but it doesn't offer any reliable reference or papers. I urgently want to konw how to prove it or whether there are any publications to verify its NP-hard. Thanks in advance.

$\endgroup$
1
  • $\begingroup$ If you have a solution for the problem with K subsets, it's quite trivial to use this to solve the other problem. I would be surprised if anyone wasted time to put this in a paper. $\endgroup$
    – gnasher729
    Nov 8 at 9:44

1 Answer 1

0
$\begingroup$

Here is a proof that the problem is weakly NP-hard. I don't know if you'll find it in any paper since it is quite simple.

Consider the decision version of your problem: given a (multi-)set $A=\{a_1, \dots, a_L\}$ of $L$ elements, a positive integer $K$, and an integer $z$ decide whether there exists a partition of $A$ into $K$ sets $S_1, \dots, S_K$ such that $\max_{i=1, \dots, K} \sum_{x \in S_i} x \le z$.

To show that your problem is NP-hard we reduce PARTITION to the decision version your problem. Let $X = \{x_1, \dots, x_n\}$ be an instance of partition. Consider the instance with $L=n$, $a_i = x_i$, $K=2$, and $z=\frac{1}{2} \sum_{i=1}^L a_i$.

If the PARTITION instance is a yes-instance, then there is a partition $X_1, X_2$ of $X$ such that $\sum_{x \in X_1} x = \sum_{x \in X_2} x = \frac{1}{2} \sum_{x \in X} x = z$. Then choosing $S_1 = X_1$ and $S_2 = X_2$ yields a solution with $\max\left\{ \sum_{x \in S_1} x, \sum_{x \in S_2} x \right\} = z$, showing that the instance of your problem is a yes-instance.

If the instance to your problem is a yes-instance, then there must be some partition $S_1, S_2$ of $A$ such that $\max\left\{ \sum_{x \in S_1} x, \sum_{x \in S_2} x \right\} x \le z$ which implies $\sum_{x \in S_1} x = \sum_{x \in S_2} x = z = \frac{1}{2} \sum_{i=1}^L a_i = \frac{1}{2} \sum_{x \in X} x$. Therefore the PARTITION instance is a yes-instance.


You can also show that the problem is strongly NP-hard by reducing from a variant of 3-PARTITION.

Consider an instance of $3$-partition $S=\{x_1, x_2, \dots, x_{3n}\}$ with the additional constraint $\frac{T}{4} < x_i < \frac{T}{2}$, where $T = \frac{1}{n} \sum_{i=1}^{3n} x_i > 0$. The problem is known to be strongly NP-hard also in this case (see, e.g., the Wikipedia page for a reduction from the general case).

You can get an instance of (the decision version of) your problem by choosing $L=3n$, $a_i = x_i$, $K=n$, and $z=T$.

If there is a solution to the 3-PARTITION instance, then there is a partition $X_1, \dots, X_n$ of $X$ such that $\sum_{x \in X_i} x = T$ for all $i = 1, \dots, n$. Choosing $S_i = X_i$ yields a solution to your problem with $\max_{i=1, \dots, K} \sum_{x \in S_i} x = T = z$.

If there is a solution $S_1, \dots, S_n$ to the instance of your problem, then each set $S_i$ must contain at most $3$ elements, since otherwise we would have $\sum_{x \in S_i} x > |S_i| \cdot \frac{T}{4} \ge 4 \cdot \frac{T}{4} = T = z$. Consequently, all sets must have exactly $3$ elements (if at least one set $S_i$ had at most $2$ elements, then there would be some other set with at least $4$ elements). Since this is a yes instance, we have $\sum_{x \in S_i} x \le z = T$ for all $i=1,\dots,n$, which implies $\sum_{x \in S_i} x = T$ (if at least one set $S_i$ had $\sum_{x \in S_i} x < T$ then there would be some other set $S_j$ with $\sum_{x \in S_j} x > T$). This shows that the 3-PARTITION instance is a yes-instance.

$\endgroup$

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.