1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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})$). $\endgroup$
    – Dmitry
    Nov 15, 2021 at 10:22
  • $\begingroup$ 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 $\endgroup$
    – Fish_n_Chips
    Nov 15, 2021 at 13:29
  • $\begingroup$ You can generalize en.wikipedia.org/wiki/…. But, given your numbers, the runtime I outlined above is pretty hopeless. $\endgroup$
    – Dmitry
    Nov 15, 2021 at 14:09
  • $\begingroup$ 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. $\endgroup$
    – Dmitry
    Nov 15, 2021 at 14:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dmitry
    Nov 15, 2021 at 14:27

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for the explanation. But is there a better approach than brute force? I mean can this problem be solved in fewer steps compared to an exhaustive search? $\endgroup$
    – Fish_n_Chips
    Nov 15, 2021 at 11:03
  • $\begingroup$ It's quite similar to bin packing. Bin packing can use some tricks for handling very small and very large item, and they can be adapted. $\endgroup$
    – gnasher729
    Nov 15, 2021 at 11:24

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.