Dynamic programming with convexity, concavity and sparsity

Dynamic programming is a general problem-solving technique that has been widely used in various fields such as control theory, operations research, biology and computer science. In many applications dynamic programming problems satisfy additional conditions of convexity, concavity and sparsity. This paper presents a classification of dynamic programming problems and surveys efficient algorithms based on the three conditions.

Authors

• Zvi Galil
• Kunsoo Park

Keywords

No keywords are indexed for this paper.