4 added 92 characters in body
source | link

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]$).

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$.

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]$).

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]$).

3 improved formatting
source | link

Let $S^*_j$ be the sum of the the elements in the $j$-th subarray in an optimal solution and guess $m^* = \min\limits_j S^*_j$$m^* = \min_j S^*_j$.

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\limits_i S_i & \mbox{if } \min\limits_i S_i \ge m^* \\ +\infty & \mbox{ otherwise.} \end{cases} $$$$ \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} \max\, \{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \} & \mbox{if } \sum_{h=j+1}^i x_i \ge m^* \\ +\infty & \mbox{otherwise} \end{cases}. $$$$ 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]$).

Let $S^*_j$ be the sum of the the elements in the $j$-th subarray in an optimal solution and guess $m^* = \min\limits_j S^*_j$.

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\limits_i S_i & \mbox{if } \min\limits_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} \max\, \{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \} & \mbox{if } \sum_{h=j+1}^i x_i \ge m^* \\ +\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]$).

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$.

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]$).

2 improved formatting
source | link

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$$m^* = \min\limits_j S^*_j$.

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} $$$$ \begin{cases} \max\limits_i S_i & \mbox{if } \min\limits_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, \dots, i-1} \begin{cases} \max \{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \} & \mbox{if } \sum_{h=j+1}^i x_i \ge m^* \\ +\infty & \mbox{otherwise} \end{cases}. $$$$ OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1} \begin{cases} \max\, \{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \} & \mbox{if } \sum_{h=j+1}^i x_i \ge m^* \\ +\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]$).

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$.

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, \dots, i-1} \begin{cases} \max \{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \} & \mbox{if } \sum_{h=j+1}^i x_i \ge m^* \\ +\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]$).

Let $S^*_j$ be the sum of the the elements in the $j$-th subarray in an optimal solution and guess $m^* = \min\limits_j S^*_j$.

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\limits_i S_i & \mbox{if } \min\limits_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} \max\, \{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \} & \mbox{if } \sum_{h=j+1}^i x_i \ge m^* \\ +\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]$).

1
source | link