How can I improve my algorithm for finding optimally balanced P-way partitioning of array

Question

I have an array of $N$ weights $w_i$, say $w_i=\{4, 5, 12, 16, 3, 10, 1\}$, and I need to divide this array into $P$ partitions such that partitions are optimally balanced, i.e. that maximum sum of weights of any partition is as small as possible. Luckily the problem is constrained by the fact that the weights can't be reordered. If the number of partitions is three, the above example would give the optimal partitions: $\{4, 5, 12\}, \{16\}, \{3, 10, 1\}$.

I have found efficient recipes (e.g. partition problem, subset sum, Optimal Partition of Book Chapters, A partition algorithm, An algorithm for k-way array partitioning) for many similar problems for the cases where the weights are unordered sets and/or the number of partitions is fixed at 2 or 3, but none that seem to exactly address my problem where the number of partitions is arbitrary.

I have solved the problem myself using divide-and-conquer algorithm (written in Python below), but it seems to be awfully slow for many partitions (e.g. N=100, P=8). So I was thinking that there got to be a better way, using dynamic programming or some other clever tricks?

Does anyone have any suggestions?

Slow Python divide-and-conquer algorithm:

def findOptimalPartitions(weights, num_partitions):
    if num_partitions == 1:
        # If there is only one partition, it must start at the first index
        # and have a size equal to the sum of all weights.
        return numpy.array([0], dtype=int), sum(weights)

    # Initially we let all partitions start at zero, meaning that all but the
    # last partition gets zero elements, and the last gets them all.
    partition_offsets = numpy.array([0] * num_partitions)
    max_partition_size = sum(weights)

    # We now divide the weigths into two partitions that split at index n.
    # We know that each partition should have at least one element, so there
    # is no point in looping over all elements.
    for n in range(1, len(weights) - num_partitions):
        first_partition_size = sum(weights[:n])

        if first_partition_size > max_partition_size:
            # If the first partition size is larger than the best currently
            # found, there is no point in searching further.
            break

        # The second partition that starts at n we now further split into
        # subpartitions in a recursive manner.
        subpartition_offsets, best_subpartition_size = \
            findOptimalPartitions(weights[n:], num_partitions - 1)

        # If the maximum size of any of the current partitions is smaller
        # than the current best partitioning, we update the best partitions.
        if ((first_partition_size < max_partition_size)
                and (best_subpartition_size < max_partition_size)):
            # The first partition always start at 0. The others start at
            # ones from the subpartition relative to the current index, so
            # add the current index to those.
            partition_offsets[1:] = n + subpartition_offsets
            # Find the maximum partition size.
            max_partition_size = max(first_partition_size, best_subpartition_size)

    return partition_offsets, max_partition_size

EDIT: A trivial Greedy algorithm where the last partition will typically be too large.

def greedyPartition(weights, num_partitions):
    target_size = sum(weights) / num_partitions

    partition_offsets = numpy.zeros(num_partitions, dtype=int)
    partition_sizes = numpy.zeros(num_partitions, dtype=int)
    current_divider = 0
    for p in range(0, num_partitions - 1):
        partition_size = 0
        for n in range(current_divider, len(weights)):
            if partition_size + weights[n] > target_size:
                current_divider = n
                partition_offsets[p + 1] = current_divider
                partition_sizes[p] = partition_size
                break

            partition_size += weights[n]
    partition_sizes[-1] = sum(weights) - sum(partition_sizes[:-1])
    max_partition_size = max(partition_sizes)

    return partition_offsets, max_partition_size

Answer 1

Binary search is a general strategy that can often be applied to problems that seeks a single optimized number as an answer.

---

Let $A=[a_1, \cdots, a_N]$ be the given array of weights. Assume $1\lt P\lt N$; otherwise, the problem becomes trivial.

Given a weight $w$ such that $1\le w\le\sum a_i$, we can associate a partition $\mathcal P(w)$, $A = P_1\,P_2\,\cdots P_m$ such that

1. Subarray $P_1$ is as long as possible such that the sum of all weights in it is no more than $w$.
2. Then subarray $P_2$ is as long as possible such that the sum of all weights in it is no more than $w$.
3. Then subarray $P_3$ is as long as possible such that the sum of all weights in it is no more than $w$.
4. And so on.
5. Finally, we are left with non-empty subarray $P_m$, the sum of all weights in which is no more than $w$.

Note that $m=\#\mathcal P(w)$ is the minimum number of subarrays in a partition where the sum of all weights in every subarray is at most $w$. We want to find $w$ such that $\#\mathcal P(w)=P$ and $\#\mathcal P(w+1)<P$. Since the map from $w$ to $\mathcal P(w)$ is decreasing, we can use binary search to find it.

Here is the outline of an algorithm that finds the largest $w$ such that $\mathcal P(w)=P$. Assume the given weights are integers; otherwise, we need to tweak the algorithm a bit. .

1. Let $ma=\max\{a_i\}$. If $P\ge \#\mathcal P(ma)$, the least maximum sum is $ma$. Deal with this easy case and return.

2. Let $low=ma$ and $high=\sum a_i$.

3. If $low\lt high-1$, $ mid = (low + high)//2$ and compute $m= \#\mathcal P(mid)$.

   • If $m\le P$, lower $high$ to $mid$.
   • If $m\gt P$, raise $low$ to $mid$.

   Go back to the start of this step.

4. Let $H$ be the partition $\mathcal P(high)$. If $\#H\not= P$, divide some subarrays of $H$ into smaller subarrays so as to increase the number of subarrays by $P-\#(P)$. Return $H$.

The loop invariant for step 3 is $\#\mathcal P(low)>P$, $\#\mathcal P(high)\le P$ and $low\le high-1$. When the loop ends, i.e., when $low==high-1$, we must still have $\#\mathcal P(low)>P$ and $\#\mathcal P(high)\le P$. That means, $high$ is the minimum of the maximum sum of weights of any subarray in a partition of size no more than $P$, which explains largely why this algorithm is correct.

---

This algorithm runs in $O(N\log(\sum a_i))$ time, since the most of time is spent on computing $\mathcal P(w)$ and it takes $O(N)$ time to compute $\mathcal P(w)$ for any given weight $w$.

---

Exercise (the dual problem). Given an array of $N$ positive integer weights $w_i$ and an integer $P$, divide the array into $P$ parts such that the parts are optimally balanced, i.e. that minimum sum of weights of any part is as large as possible.