Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
7543784 | Operations Research Letters | 2018 | 8 Pages |
Abstract
Many dynamic programming algorithms for discrete optimization problems are pure in that they only use min/max and addition operations in their recursions. Some of them, in particular those for various shortest path problems, are even incremental in that one of the inputs to the addition operations is a variable. We present an explicit optimization problem such that it can be solved by a pure DP algorithm using a polynomial number of operations, but any incremental DP algorithm for this problem requires a super-polynomial number of operations.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Stasys Jukna,