Please use this identifier to cite or link to this item:

Online dynamic programming speedups

Authors Bar-Noy, A.
Golin, M.J. View this author's profile
Zhang, Y.
Issue Date 2009
Source Theory of Computing Systems , v. 45, (3), 2009, p. 429-445
Summary Consider the dynamic program h(n) = min1≤j≤n a(n, j), where a(n, j) is some formula that may (online) or may not (offline) depend on the previously computed h(i), for i < n. The goal is to compute all h(n), for 1 ≤ n ≤ N. It is well known that, if a(n, j) satisfy the Monge property, then the SMAWK algorithm (Aggarwal et al., Algorithmica 2(1):195-208, 1987) can solve the offline problem in O(N) time; a Θ(N) speedup over the naive algorithm.In this paper we extend this speedup to the online case, that is, to compute h(n) in the order n = 1, 2, . . . , N when (i) we do not know the values of a(n′ , j) for n′ > n before h(n) has been computed and (ii) do not know the problem size N in advance. We show that if a(n, j) satisfy a stronger, but sometimes still natural, property than the Monge one, then each h(n) can be computed in online fashion in O(1) amortized time. This maintains the speedup online, in the sense that the total time to compute all h(n) is O(N). We also show how to compute each h(n) in the worst case O(log N) time, while maintaining the amortized time bound. For a(n, j) satisfying our stronger property, our algorithm is also simpler than the standard SMAWK algorithm for solving the offline case. We illustrate our technique on two examples from the literature; the first is the D-median problem on a line, and the second comes from mobile wireless paging. © Springer Science+Business Media, LLC 2009.
ISSN 1432-4350
Language English
Format Article
Access View full-text via DOI
View full-text via Scopus
View full-text via Web of Science