Reducing time complexity in maximal minimum-sum 2-partitioning of an array

Question

Let array[N] an array of N non-negative values. We're trying to recursively partition the array in two (2) subarrays, so that we can achieve the maximum "minimum-sum" of each subarray. The solution is described by the following recursion:

enter image description here

We want to calculate opt[0][N-1].

Let c[x][y] denote the sum{array[i]} from x up to y (including). I have managed to unwind the recursion in the following C++ code snippet, using dynamic programming:

for ( uint16_t K1 = 0; K1 < N; K1 ++ ) {
    for ( uint16_t K2 = 0; K2 < N-K1; K2 ++ ) {

        const uint16_t x = K2, y = K2 + K1;
        opt[x][y] = 0;

        for ( uint16_t w = x; w < y; w ++ ) {

            uint32_t left  = c[x][w]   + opt[x][w];
            uint32_t right = c[w+1][y] + opt[w+1][y];

            /* Choose minimum between left-right */
            uint32_t val = MIN( left, right );

            /* Best opt[x][y] ? */
            if ( val > opt[x][y] ) {
                opt[x][y] = val;
            }
        }

    } /* K2 */
}     /* K1 */

This technique parses all subarrays, beginning from size 1 and up to size N. The final solution will thus be stored in opt[0][N-1].

For example, if N=6, the matrix will be iterated as follows: (0,0) (1,1) (2,2) (3,3) (4,4) (5,5) (0,1) (1,2) (2,3) (3,4) (4,5) (0,2) (1,3) (2,4) (3,5) (0,3) (1,4) (2,5) (0,4) (1,5) (0,5). The final answer will be in opt[0][5].

I have tested and verified that the above technique works to unwind the recursion. I am trying to further reduce the complexity, as this will run in O(n^3), if I'm correct. Could this be achieved?

edit: I'm also noting the physical meaning of the recursion, as it was asked in the comments. Let N denote N cities across a straight line. We're a landlord who controls these cities; at the end of a year, each city i pays an upkeep of array[i] coins as long as it's under our control.

Our cities are under attack by a superior force and defeat is unavoidable. At the beginning of each year, we erect a wall between two adjacent cities i,i+1, x <= i <= y. During each year, the enemy forces will attack either from the west, thus conquering all cities in [x,i], or will attack from the east, thus conquering all cities in [i+1,y]. The remaining cities will pay us their upkeep at the end of the year. The enemy forces destroy the wall at the end of the year, retreat, and launch a new attack in the following year. The game ends when only 1 city is left standing.

The enemy forces will always attack from the optimal position, in order to reduce our maximum income over time. Our strategy is to choose the optimal position of the wall, so as to maximize our total income at the end of the game.

This is similar to dp in matrix multiplication it wont work here — sashas
IOW you are trying to break a set in two subsets with sums as close to being equal as possible. Am I right? This doesn't look like it has a known polynomial-time solution. — n. 1.8e9-where's-my-share m.
@n.m It's not hard if the subsets have to be contiguous, like in this case. Also the recurrence looks a little bit more involved than that — Niklas B.
@NiklasB sorry I don't follow. How is this different from the set partition or subset-sum problems? — n. 1.8e9-where's-my-share m.
FWIW, let w(x,y) be the optimal w in your definition of opt(x,y). I conjecture that there is a solution with w(x,y+1) >= w(x,y) in all cases and that the right side of your recurrence is convex in w. This lets you remove one factor of n in the time complexity, giving you O(n^2), by fixing an x and then computing the y in increasing order. — Niklas B.

Adama Adama · Accepted Answer · 2014-12-22T21:27:04

Here's the final answer to the problem, following the contribution of @NiklasB. . Let w(x,y) denote the optimal partition of an array for the problem opt[x][y]. As follows, x <= w(x,y) < y. We assume that the positions for all subproblems opt[x][y] with a given subarray size d = y-x are known.

Let's now try to find the optimal w positions for all subproblems of size k+1. We can easily prove that w(x,y+1) >= w(x,y); IOW if we add another element to the right, the optimal partition might "move to the right", in order to more evenly balance the two sums; it however cannot "move to the left". In a similar fashion, w(x-1,y) <= w(x,y).

NB: it would be helpful if someone could attempt to mathematically verify the above.

As follows, let wall[x][y] denote the optimal w solution for the subproblem opt[x][y]. Loop for ( uint16_t w = x; w < y; w ++ ) in the original snippet, will be modified as follows:

for ( uint16_t w = wall[x][y-1]; w <= wall[x+1][y]; w ++ ) {
  ...
  if ( val > opt[x][y] ) {
    opt[x][y] = val;
    wall[x][y] = w;
  }
}

A few modifications are needed to deal with corner cases when 0 <= y-x <= 1, but it does the job. It reduces the running time complexity from O(n^3) to O(n^2), since the time to compute the solution for a larger subproblem is amortized O(1), by taking into account the w boundaries. Example: with N = 2500, the recursive algorithm (with memoization) runs in 58 sec. The O(n^2) algorithm runs in only 148 msec.

Reducing time complexity in maximal minimum-sum 2-partitioning of an array

1 Answers