"A simple linear time algorithm" by Klawe

Question

I try to implement the algorithm described in "A simple linear time algorithm for concave one-dimensional dynamic programming" by Maria M. Klawe, 1989.

However, right at the beginning there is possibly a typo:

i ← 0; r ← 0;
While i < 2^⎡log(n + 1)⎤ and r < i do;
    If i = 2^⎡log i⎤ - 1 then do;
...

because of the "r < i" the while loop immediately terminates. Also, the "if" condition should be taken right in the first loop (from what I understood).

Please, does anyone know if there is a typo indeed and eventually what should the initialization look like?

Edit

I hope it's ok if I post here the whole algorithm. I honestly don't know what the practice on posting such things online is - if it's not ok, I apologize and I (or the moderator) will delete it.

i ← 0; r ← 0;
While i < 2^⎡log(n + 1)⎤ and r < i do;
    If i = 2^⎡log i⎤ - 1 then do;
        SMAWK M(0 : i, i + 1 : min(2(i + 1) - 1, n));
        * a square has been treated *
        i ← i + 1;
        end;
    else if M(r, 2^(⎣log(i + 1)⎦ + 1) - 1) < M(i, 2^(⎣log(i + 1)⎦ + 1) - 1)
        then i ← i + 1;
        * a slice has been treated *
        else r ← r + 1;
        * the region M(r, 2^(⎣log(i + 1)⎦ + 1) - 1 : n) has been treated *
end;
* The algorithm has now treated rows 0, ..., i - 1. *

It works like this: there is a triangular matrix, which the algorithm extracts larger and larger squares from (that's the first branch). The algorithm then breaks the remaining lines under the square into "slices".

PS: The initialization is just one problem. The another is that for some input the second branch M(r, ...) < M(i, ...) starts to increase only r which causes the while loop to exit prematurely because of r < i

Answer 1

There is also pseudocode for this algorithm given on p. 14 of Aggarwal and Tokuyama, "Consecutive interval query and dynamic programming on intervals." Discrete Applied Math 85 (1998). It starts out:

1: i=0;
2: r=min{n,2^(i+1)};

and has other differences from the pseudocode that you posted; at first sight, the Aggarwal and Tokuyama pseudocode seems quite a bit clearer. So it seems likely there was a typo in the original. Hopefully, this second paper gets the pseudocode correct. It certainly gives a good enough explanation of the algorithm for me to understand it and see why it works.

UPDATE: (Twice, now): The first update gave the response to questions in the comments. In the second update I corrected the restriction for when you can evaluate a cell. Here's what is going on (with possible fencepost errors in my explanation).

If you search A[j,j;n,n], you never have to search another square, you're done. That's what "5.2.3: Exit" means. You're not exiting the loop; you're exiting the program.

Why do you need to search A[j,j,n,n]? You have just found the minima of columns 2^i to r over rows 1 ... 2^i+1. Here 2^i + 1 <= j <= 2^(i+1). Because of the entries you've looked at in column r and the monotonicity of the matrix, you can conclude that you've already found the minimum in columns 1 through j-1, and the minimum in columns j..r is either the one you've already found or is in the matrix A[j,j;n,n]. Thus, you have to search A[j,j;n,n], and for the columns between j and r, you need to compare the minimum you find in A[j,j;n,n] with the minimum you've already found for that column (this comparison is step 5.2.2.1).

You can't evaluate an entry A[s,t] until for every column 1..s, you know the minimum in that column. Thus, in order to evaluate an entry A[s,t] when you're searching A[j,j;n,n], you first need to find the minimum in column s. This is why you need to run 5.2.1 and 5.2.2 concurrently. This means you can stop the concurrent 5.2.2 process when you reach column r. (You can see this because 5.2.2.1 says "j <= t <= r".)

So I guess this means that as soon as you find the minimum in column t in 5.2.1, you have to pass it to 5.2.2, do the comparison of the two candidate minima in column t, and now that you know the minimum in column t, you can use it to evaluate entries in row t. Technically, you could do this comparison any time between the point at which you know the minimum of column t in A[j,j;n,n], and the first point at which you need to evaluate a cell in row t. Offhand, I don't see any reason not to do it as soon as you learn the minimum of column t in A[j,j;n,n].