# Partition a set of n integers into m subsets in a way that the maximum subset sum is minimized

Let's say we have a set of n integers. I'm trying to find a way to partition this set into m subsets (empty subsets are not allowed), so that the maximum subset-sum gets minimized. for example, let's say we have the following set and m = 2:

{11, 5, 11, 5, 10}

the optimal partitioning will be as follows:

{5, 5, 11}, {10, 11}

where the maximum of subset-sums is 21 (no other partition reaches a smaller maximum subset-sum).

The brute force approach will generate all such partitions and find the minimum max sum among them. But is there a better approach to solve this? I was thinking of a backtracking algorithm but I have no idea where to start. I'm only interested in the minimum maximum sum among all partitions and not the partition itself.

• Do you have any additional constraints? If $m$ is very small and your weights are small integers, then you can solve this by generalizing a standard dynamic programming approach for subset-sum (with running time something like $O(num\_items \cdot max\_weight^{m-1})$). Nov 15, 2021 at 10:22
• m, n will not be bigger than say 20. Integers are all positive and less than 125000. Can you elaborate on your solution, please? @Dmitry Nov 15, 2021 at 13:29
• You can generalize en.wikipedia.org/wiki/…. But, given your numbers, the runtime I outlined above is pretty hopeless. Nov 15, 2021 at 14:09
• I think there is hope for a brute-force approach with the following optimization: 1) you guess the answer $a$, and check whether you can get the maximum less than the answer $a$. 2) You process $a$ in decreasing order. There is a chance that the only $a$'s which will take a while are the ones close to the correct answer. With a bunch of other optimizations, it may work out somehow. Nov 15, 2021 at 14:16
• BTW, your problem is equivalent to en.wikipedia.org/wiki/Identical-machines_scheduling. You can check what the literature says about solving it. Probably, your best practical approach would be to use an Integer Linear Programming solver. Nov 15, 2021 at 14:27

The problem can be shown to be weakly NP-hard by noticing that it is a generalization of partition. In particular, when $$m=2$$ the input set of integers is a yes instance of partition if and only if the measure of an optimal solution of your problem equals half the sum of the integers.
The problem can also be shown to be strongly NP-hard by noticing that it is a generalization of 3-partition in the special case in which all the integers in the input set $$S$$ are positive and strictly between $$\frac{1}{4}\sum_{s \in S} s$$ and $$\frac{1}{2}\sum_{s \in S} s$$. In particular, we can assume that $$|S|$$ is a multiple of $$3$$. When $$m=|S|/3$$ the optimal solution to your problem has measure $$\frac{3}{|S|}\sum_{s \in S} s$$ if and only if the 3-partition instance is a yes instance.