A Simple Linear Time Algorithm for Concave One-Dimensional Dynamic Programming

ID
TR-89-16
Authors
Maria M. Klawe
Publishing date
January 1989
Abstract

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.