How to prove this variant of set partition problem is NP hard?

Question

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.

Answer 1

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.