Given the tuple (list, value):

$$\left(\left[x_1, x_2, \cdots x_n\right], y\right)$$

You may choose two adjacent values in the list to modify the tuple as:

$$\left(\left[x_1, x_2, \cdots x_{i-1}, (x_i + x_{i+1}), x_{i+2} \cdots x_n\right], y + x_{i} + x_{i+1}\right)$$

Iterate until:

$$\left(\left[\sum_i x_i\right], y + z\right)$$

What is the optimal set of choices that minimizes $z$?

Intuitively, you never want to operate on the largest number in the list. But the largest number in this list changes as you add values together. In other words, the optimal solution is not necessarily obtained by an optimal solution of a sub-problem.

A greedy solution would start by taking the smallest number in this list and adding it to the smaller of its adjacent numbers. This solution, while close, is not equivalent to the value returned by brute force search. This points to the fact the some locally optimal step is not globally optimal, which could be connected to the fact that the largest element of the list changes as values are added together.

  • 1
    $\begingroup$ Do you mean the product of $x_{i+2},\ldots,x_n$ by $x_{i+2}\cdots x_n$? $\endgroup$
    – xskxzr
    Oct 4 '19 at 3:00
  • 1
    $\begingroup$ What does the modification do if the value is not zero? Does it add $x_i+x_{i+1}$ to the value? Can you edit the question to specify that? $\endgroup$
    – D.W.
    Oct 4 '19 at 3:50
  • $\begingroup$ Have you tried using dynamic programming? See cs.stackexchange.com/tags/dynamic-programming/info for some guidance on applying it. Where did you encounter this problem? Can you edit the question to state where you encountered it and provide a source if you saw it somewhere? $\endgroup$
    – D.W.
    Oct 4 '19 at 3:51
  • $\begingroup$ Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Oct 4 '19 at 3:52
  • $\begingroup$ Dynamic programming doesn't work since the subproblems change. You could hash the list, but it still doesn't break down nicely. $\endgroup$
    – user18764
    Oct 4 '19 at 4:06

I will assume that initially $y=0$, as this makes no difference in your problem.

Look at the very last two elements $a,b$ that you will apply your operation on: The tuple is $([a,b], y$) and, at the next iteration, it will necessarily be $([a+b], $y+a+b$)$, since $a+b = \sum_{i=1}^n x_i$ is a constant, you only want to minimize $y$.

Notice that $a$ (resp. $b$) must have been obtained as a sum of some contiguous sequence of elements of your list starting from $x_1$ (resp. ending in $x_n$).

Calling $OPT[i,j]$ the minimum value of $y+z=z$ in your problem when the input instance consists of $([x_1, \dots, x_j], 0)$, we then obtain (for $n > 1$):

$$ OPT[1,n] = \sum_{h=1}^n x_h + min_{h=1,\dots,n-1} \left\{ OPT[1,h] + OPT[h+1,n] \right\} $$

and, in general:

$$ OPT[i,j] = \begin{cases} \sum_{h=i}^j x_h + min_{h=i,\dots,j-1} \left\{ OPT[i,h] + OPT[h+1,j] \right\} & \mbox{if } j-i>0 \\ 0 & \mbox{if } j-i = 0 \end{cases}. $$

There are $O(n^2)$ subproblems and each requires taking a minimum over $O(n)$ elements, so your problem can be solved in $O(n^3)$ time via dynamic programming.

  • $\begingroup$ Should it not be $OPT[i,h-1] + OPT[h,j]$? $\endgroup$
    – user18764
    Oct 5 '19 at 2:44
  • $\begingroup$ Fixed :) It is $OPT[i,h] + OPT[h+1,j]$ since $h$ ranges from $1$ to $j-1$. $\endgroup$
    – Steven
    Oct 5 '19 at 9:14
  • $\begingroup$ Great answer! I couldn't get that first assumption correct. But it is now painfully obvious. I am curious how well this solution works if the "addition" is approximate. I am trying to use this to optimize a foldl operation with approximate linear complexity. $\endgroup$
    – user18764
    Oct 5 '19 at 12:05

Your problem is known as optimal alphabetic binary tree (or various similar names). This is an ordered version of Huffman coding, in which the two numbers being added don't have to be adjacent. The problem can be solved in $O(n\log n)$ using either the Hu–Tucker algorithm or the Garsia–Wachs algorithm.


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.