1
$\begingroup$

I started thinking about this problem while trying to find the best way to divide a book reading into $4$ roughly equal sections. I ended up brute-forcing every possible combination, but now I'm wondering if there's a more efficient way to do this and what it might be.

After a bit of wordsmithing, I came up with this way to formally state the problem: Given a strictly increasing list $L$ containing $n$ positive real numbers, what is the most efficient algorithm to find the optimal way to partition the list into $m$ segments minimizing the mean absolute deviation of the list containing the length of each segment; where two subsequent numbers in $L$ define a segment, its length is calculated by subtracting the first and last elements, and segments must start directly after one another? As an example for the indices, for $L=[1,2,5,9,10,12,15,19,21,30,32]$ and $m=3$, a useful partition would be $([1, 12], [12,  21], [21, 32])$, although it should be noted that this is not the optimal partition for that list, it's just an example for indices.

For clarification, this is the more informal way of putting it: What is the most efficient algorithm to find the best way to partition a list into segments that are as equal in length as possible? Please include a proof that your algorithm is the most efficient and its big O time complexity in your answer.

A proof that the question is NP-hard and ergo hard to prove optimality for would also be accepted as an answer. Also, if you can find a more optimal algorithm than the current answer even without a proof, that would also be appreciated.

Improve this question
$\endgroup$
7
  • $\begingroup$ Hm. Let the range $r$ be the difference between last and first number. What if I find one or two numbers equal to or "containing" first number + $r/m$, same for last, and recurse? $\endgroup$ Commented Aug 27 at 8:24
  • $\begingroup$ I don't know about "most efficient" but dynamic programming solution seems possible and efficient enough. You definition of the length of a segment looks incomplete. Isn't the length of a segment the absolute difference between its first and last element? $\endgroup$ Commented Aug 28 at 16:20
  • $\begingroup$ Can you give an example? the question is not very clear to me right now... $\endgroup$ Commented Aug 28 at 21:14
  • $\begingroup$ @JacobHungerford, maybe we understand the word "example" differently, but I meant an example of an input and output of the problem. Like if $L = [1,2,5,9,10, 12, 15, 19, 21, 30, 32]$ and $m = 3$, what is the output? $\endgroup$ Commented Aug 29 at 13:50
  • 1
    $\begingroup$ Taking Bernardo Subercaseaux's example, is a useful partition ([1, 12), [12,  21), [21, 32)), or ([1, 9]), [10,  19], [21, 32])? $\endgroup$ Commented Nov 14 at 8:06

2 Answers 2

Reset to default
2
$\begingroup$

As @Li-yao Xia commented, this can be solved with pseudo-polynomial dynamic programming. The indices are a bit tricky in this problem, so hopefully at least the gist of this answer is correct, but I might be wrong on some indices.

Let me formalize things a bit first. We are given a list of numbers $L$ of length $n$, and we seek to partition as $L[0.. i_1), L[i_1.. i_2), \ldots, L[i_{m-1}.. n)$ with the goal of minimizing the objective described next. The "length" of the $j$-th part $L[i_j, i_{j+1})$ is $\lambda_j := L[i_{j+1} - 1] - L[i_j]$, and the average length is $\bar {\lambda} = \frac{1}{m}\sum_{j=0}^{m-1} \lambda_j$. The objective to minimize is then $\frac{1}{m}\sum_{j=0}^{m-1} |\lambda_j - \bar{\lambda}|$, and obviously we can ignore the $\frac{1}{m}$.

First, let's note that a telescopic argument yields $$ m \bar{\lambda} = \sum_{j=0}^{m-1} L[i_{j+1} - 1] - L[i_j] = (L[n-1] - L[0]) + \left(\sum_{j=1}^{m-1} L[i_j - 1] - L[i_j]\right), $$ and we will denote the last term $\left(\sum_{j=1}^{m-1} L[i_j - 1] - L[i_j]\right)$ by $G$, noting that $G$ depends on the choice of segmentation. Note that knowing $G$, the cost $C_G(a, b)$ of a segment $L[a..b)$ is $$ C_G(a, b) := |(L[b-1] - L[a]) - \bar{\lambda}| = \left|(L[b-1] - L[a]) - \frac{(L[n-1] - L[0]) + G}{m}\right| $$

Let us not denote by $f(i, j, g)$ what the optimal answer is for input $L[0..i)$, using $m := j$ segments, and constrained to have $G = g$. Then, the base case is that

$$ f(i, 1, g) = \begin{cases} C_g(0, i) & \text{if } g = 0\\ \infty & \text{otherwise}, \end{cases} $$ and the key recursive equation is $$ f(i, j, g) = \min_{1 \leq k \leq i-j+1} \left\{ f(i-k, j-1, g - (L[i-k] - L[i-k+1])) + C_g(i-k, i) \right\}. $$

Naturally, the final optimal answer is $\min_g f(n, m, g)$, and since $g$ can only take values in $(-\sum_{j=1}^{n-1} L[j] - L[j-1] , 0)$. Running this dynamic program for each possible $g$ yields a pseudo-polynomial time algorithm. Concretely, if all values of $L$ are integers, then $g$ can take at most $\max(L)$ values (as $\sum_{j=1}^{n-1} L[j] - L[j-1] = L[n-1] - L[0] \leq \max(L)$), and we get an algorithm of complexity $O(n^2 m \max(L))$ (since the DP table has size $nm\max(L)$, but each step iterates over $k$ which takes $n - m = O(n)$ different values). For real values, if $\delta := \min_i L[i+1] - L[i]$, then $g$ can take at most $\max(L)/\delta$ possible values, so we can get complexity $O(n^2 m \max(L)/\delta)$. I don't know if this is optimal, or whether the problem is weakly NP-hard.

$\endgroup$
3
  • $\begingroup$ can you show that this is truly the most efficient algorithm possible(or show that it is NP-hard or hard to prove perfection in some other way) $\endgroup$ Commented Aug 29 at 15:54
  • $\begingroup$ @JacobHungerford I tried for a bit, but unfortunately couldn't prove NP-hardness. I added the complexity details of the algorithm I gave, but I don't know if it's optimal (I actually doubt it). Feel free to not mark it as accepted if it doesn't answer your question fully. (You can always upvote if it's helpful but not yet a satisfactory answer). $\endgroup$ Commented Sep 14 at 15:54
  • $\begingroup$ I just noticed, since I recently updated my question to clarify the indices, you can update the indices in your answer now if you want. $\endgroup$ Commented Nov 25 at 17:20
0
$\begingroup$

Your problem is known as multiway number partitioning. It contains the partition problem as a special case, and so it has been known to be NP-hard since 1972.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I just looked at both of those, and they are about the sum of the elements in each subset, which is not the way my problem is worded, mine is about ensuring each segment has lengths that are as equal as possible $\endgroup$ Commented Nov 5 at 14:42

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.