Technical Reports

The ICICS/CS Reading Room


UBC CS TR-89-16 Summary

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.