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

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.

• 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. Nov 8 at 9:44

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.