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?
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