# The ICICS/CS Reading Room

## UBC CS TR-89-16 Summary

- No on-line copy of this technical report is available.

- A Simple Linear Time Algorithm for Concave One-Dimensional Dynamic Programming, January 1989 Maria M. Klawe
Following [KK89] we will say that an algorithm for finding the column minima of a
matrix is ordered if the algorithm never evaluates the $(i,j)$ entry of the matrix until
the minima of columns $1, 2, \ldots , i$ are known. This note presents an extremely simple
linear time ordered algorithm for finding column minima in triangular totally monotone
matrices. Analogous to [KK89] this immediately yields a linear time algorithm for the
concave one-dimensional dynamic programming problem. Wilber [W88] gave the first
linear time algorithm for the concave one-dimensional dynamic programming problem,
but his algorithm was not ordered and hence could not be applied in some situations.
Examples of these situations are given in [GP89] and [L89]. Galil and Park [GP89] and
Larmore [L89] independently found quite different ordered linear time algorithms. All
of these algorithms, and ours as well, rely on the original linear-time algorithm known
as SMAWK for finding column minima in totally monotone matrices [AKMSW87]. The
constant in our algorithm is essentially the same of that of the Galil-Park algorithm, and
since our algorithm is so simple to program, we expect it to be the algorithm of choice in
implementations.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.