# "A simple linear time algorithm" by Klawe

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

• Since it seems impossible to find this technical report online, you're probably not going to get any good answers to this question. Nov 19 '11 at 17:14
• Have you tried to email the author? Nov 19 '11 at 18:42
• Yes, a few days ago. No answer so far. Nov 19 '11 at 20:34

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

• Thank you very much for the answer. I'm reading the paper since you post it, it's much more clear than the previous one. However, I still have a few more question: Why to search another square in next loop (7.) when it just searched A[j,j;n,n] (5.2.1)? Why to search A[j,j;n,n] in the first place if I'm interested in minima of columns 2^i to r? And the greatest difficulty: What does it mean to "concurrently" run 5.2.1? How exactly should 5.2.2 run if I need to run 5.2.1 as well? I mean, if I calculate first minima in 5.2.1 should I immediately pass it to 5.2.2.1? Nov 20 '11 at 19:29
• Sorry for the late reply, I re-read your detailed explanation and the paper many times. It seems to finally work now (I'm very happy!), that "concurrent process" from 5.2.2 is now implemented as one global array of all the minimas which can be written to as soon as possible (i.e. 5.3.1 does nothing). I have to test it a lot more and clean it too but it is also the most working version so far, thanks to you. You are very generous, I can't upvote you enough. Thank you. Nov 21 '11 at 22:04
• @Ecir: And of course, once you think of it, a global array of minima is clearly the right way to implement this. Good call! I'm glad I could help. Nov 22 '11 at 1:28