2
$\begingroup$

My question is similar to this splitting question, but my objective function is different.

Looking for an algorithm to split array of $n$ positive (integer) numbers into $N$ contiguous non-empty subarrays ($N<n$) of approximately same sums:

$$ \min_{\text{splits}} \,(\max_j S_j - \min_j S_j), $$ where $S_j$ is sum of numbers in $j$-th subarray $(j=1,\ldots,N)$.

E.g., best splitting of $100, 1, 1, 103, 90$ into three subarrays is $100,1,1|103|90$.

Typically $n\approx~10^6-10^8$, $N\approx 10-100$.

I suspect it would be some greedy approach...

$\endgroup$
  • $\begingroup$ If you have more than $N-1$ numbers above the arithmetic average, you can only limit the damage, anyway. $\endgroup$ – greybeard Jun 4 at 18:36
  • $\begingroup$ Please credit the source of the original problem. $\endgroup$ – Apass.Jack Jun 7 at 2:34
  • $\begingroup$ @Apass.Jack Note sure what you mean. I got this load balancing problem for MPI communication pattern of my program $\endgroup$ – user2052436 Jun 7 at 14:42
  • $\begingroup$ @user2052436 Can we assume an upper bound for all integers in the array? For example, all of them are less than 4096? $\endgroup$ – Apass.Jack Jun 7 at 16:08
  • $\begingroup$ @Apass.Jack Most integers in the array have values from 3 to 10. Outlier values up to a 1000, number of outliers is $< 0.01\%$ of total. $\endgroup$ – user2052436 Jun 7 at 17:26
2
$\begingroup$

This is a polynomial time algorithm:

Let $S^*_j$ be the sum of the the elements in the $j$-th subarray in an optimal solution and guess $m^* = \min_j S^*_j$ (there are only polynomially many choices of $m^*$).

Given a a way to split an array into $k$ contiguous subarrays of sums $S_1, \dots, S_k$, define the cost of such a subdivision as: $$ \begin{cases} \max_i S_i & \mbox{if } \min_i S_i \ge m^* \\ +\infty & \mbox{ otherwise.} \end{cases} $$

Let $OPT_{m^*}[i,k]$ the cost to split the array consisting of the first $i$ input elements into $k$ contiguous (non-empty) subarrays, and let $x_i$ be the $i$-th input element. Then, for $i,k \ge 1$, $$ OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1} \begin{cases} \displaystyle\max\, \left\{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \right\} & \mbox{if } \displaystyle\sum_{h=j+1}^i x_i \ge m^* \\[10pt] +\infty & \mbox{otherwise} \end{cases}. $$

Where $OPT_{m^*}[0][0] = 0$ and $OPT_{m^*}[i][0] = OPT_{m^*}[0][k] = +\infty$ for all $i,k > 0$.

The measure of an optimal solution to the original problem will be $OPT_{m^*}[n][N] - m^*$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $j$ chosen for each entry $OPT_{m^*}[i][k]$).

$\endgroup$
  • $\begingroup$ May I ask for the reason of the downvote? $\endgroup$ – Steven Jun 6 at 9:31
  • $\begingroup$ I did not downvote. This algorithm is not completely specified because of the uncertainty of $m^*$. "There are only polynomially many choices of $m^*$". I thought there could be exponentially many. Is a binary search on $m^*$ in order? $\endgroup$ – Apass.Jack Jun 6 at 18:13
  • $\begingroup$ $m^*$ is the minimum sum of a contiguous subarray in an optimal solution. There are only $O(n^2)$ contiguous subarrays of A. I don't think that straightforward binary search is possible since $OPT_m[n][N] - m$ may not be monotone. $\endgroup$ – Steven Jun 6 at 19:41
  • $\begingroup$ I must have misunderstood this algorithm. What is its time-complexity? $\endgroup$ – Apass.Jack Jun 6 at 21:27
  • $\begingroup$ A straightforward implementation requires O(n^2) guesses for $m^*$. For each guess $m$ there are $O(nN)$ values $OPT_m[i][k]$ to compute, each of which requires O(n) time. The overall time complexity is $O(n^4 N)$. This is definitely too large to be practical. $\endgroup$ – Steven Jun 6 at 21:38
0
$\begingroup$

For a partition $p$ of some numbers into $N$ parts, let $\delta(p)$ be the largest difference between the sums of numbers in the same part, i.e., $\delta(p)=\max_j S_j - \min_j S_j$, where $S_j$ is the sum of numbers in $j$-th part, $1\le j\le N$.

This answer gives an approximate algorithm that is about as fast as possible and as simple as possible. It return a partition $p$ such that $\delta(p)\lt 2u$, where $u$ is the maximum number in the given array of positive numbers.

An example to illustrate the approximate algorithm

Suppose we should split array $$[5, 8, 1, 2, 4, 1, 7, 3, 1, 6, 7, 10, 8, 9, 4, 2, 2, 8, 3, 5, 2, 6, 13, 11, 5, 8, 3, 5, 1, 9, 5]$$ into $N=6$ parts, subarray $p_1, p_2, p_3, p_4, p_5$ and $p_6$. Let $S_j$ be the sum of numbers in $p_j$.

The sum of all numbers in the array is $166$. The average of all $S_j$ is $avg=164/6=27.\bar3$.

  1. $S_1$ should be no less than $avg$ but as small as possible. Hence $p_1= [5, 8, 1,$$\,2, 4, 1, 7]$ and $S_1=28$.

  2. The next sum $S_2$ should be no more than $avg$ but as big as possible. Hecne $p_2= [3, 1$$, 6, 7, 10]$ and $S_2=27$.

  3. Since the average of $S_1$ and $S_2$ is greater than $avg$, the next sum $S_3$ should be no more than $avg$ but as big as possible. Hence $p_3=[8, 9,$$\,4, 2, 2]$ and $S_3=25$.

  4. Since the average of $S_1, S_2$ and $S_3$ is smaller than $avg$, the next sum $S_4$ should be no less than $avg$ but as small as possible. Hence $p_4=[8, 3,$$\, 5, 2, 6, 13]$ and $S_4=37$.

  5. Since the average of $S_1, S_2, S_3$ and $S_4$ is greater than $avg$, the next sum $S_5$ should be no more than $avg$ but as big as possible. Hence $p_5=[11, 5,$$\,8,3]$ and $S_5=27$.

  6. Finally, what remains is the last part, $p_6=[5,1,9,5]$ and $S_6=20$.

$$[\underbrace{5, 8, 1, 2, 4, 1, 7}_{p_1},\underbrace{3, 1, 6, 7, 10}_{p_2},\underbrace{8, 9, 4, 2, 2}_{p_3},\underbrace{8, 3, 5, 2, 6, 13}_{p_4},\underbrace{11, 5, 8, 3}_{p_5},\underbrace{5, 1, 9, 5}_{p_6}]$$

$\delta((p_1,p_2,p_3,p_4,p_5,p_6))=\max_j S_j - \min_j S_j=37-20=17$.

Pseudocode

Input: an array of $n$ positive numbers $a[0], a[1],\cdots, a[n-1]$ and $N$, a positive integer smaller than $n$.

Output: increasing indices $i_1,i_2, \cdots, i_{N-1}$ such that $\delta(p)<2u$, where the $j$-th part of partition $p$ is the (contiguous) subarray whose indices are between $i_{j-1}$ inclusive and $i_{j}$ exclusive, where $1\le j\le N$, $i_0=0$ and $i_N=n$. $\ \ u$ is the maximum of all $a[i]$.

Procedure:

  1. Create the array of partial sums $ps$ by $ps[0]\leftarrow 0$ and $ps[i]\leftarrow ps[i-1]+a[i-1]$ for all $1\le i\le n$.
  2. $parts\leftarrow1$. $\ \ at\_least\leftarrow\text{True}$. $\ \ j\leftarrow0$. $\ \ avg\leftarrow ps[n]/N$.
  3. While $parts<N$:
    1. If $at\_least$ is $\text{True}$, find the smallest index $k$ such that $k\gt j$ and $ps[k] \ge ps[j]+avg$. Otherwise, find the largest index $k$ such that $k\gt j$ and $ps[k]\le ps[j]+avg$.
    2. Output $k-1$.
    3. If $ps[k]\le parts\times avg$, $\ at\_least\leftarrow\text{True}$; otherwise $at\_least\leftarrow\text{False}$. $\ parts\leftarrow part+1$. $\ \ j\leftarrow k$.

We can add a bit of bookkeeping to track $\max_j S_j$ and $\min_j S_j$ so that the procedure can output $\delta(p)$ as well.

Note that this algorithm does not require $a[i]$ be an integer. It works equally well when they are floating-point numbers.

Complexity

The algorithm runs in $O(n)$ time-complexity, where $n$ is the number of elements in the given array. When $n$ is as large as $10^8$, a reasonable implementation is likely to return the result well within a second where the time to read the input is excluded.

The algorithm uses $O(n)$ working spaces. In fact, the array of partial sums is introduced only for the sake of easier description and coding. If we replace it with computing of the partial sums on demand, the algorithm will run with $O(1)$ space-complexity and the same $O(n)$ time-complexity.

Implementation in Java

Just click the "run" button to see the test result.

Exercise.

Show the partition $p$ obtained by the approximate algorithm satisfies $\delta(p)\lt 2u$ by establishing that $|S_j-avg|<u$ for all $j$.

$\endgroup$
  • $\begingroup$ Comment on step one ($S_1 $ should be no less than $avg$ but as small as possible), and step 2 ($S_2 $ should be no more than $avg$): in my example $100,1,1,103,90$, it will produce a split $100|1,1|103,90$, right? $\endgroup$ – user2052436 Jun 10 at 21:44
  • $\begingroup$ Yes. You can run the code as well. We can flip the algorithm so that $S_1$ should be no more than $avg$ but as big as possible, $S_2$ should be no less than $avg$ but as small as possible, etc. However, we cannot get a bound lower than $2u$ in general. In fact, I should have made it clear that it is assumed that $avg \ge u$ unless we allow empty part. $\endgroup$ – Apass.Jack Jun 10 at 22:00

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.