Dynamic programming with convexity, concavity and sparsity

Zvi Galil and Kunsoo Park
Theoretical Computer Science 92:49–76, 1992
Tech. report CUCS-066-90, Columbia Univ., Computer Science Dept., 1990
ftp://ftp.cs.columbia.edu/reports/reports-1990/cucs-066-90.ps.Z

Cites:

• Speeding up dynamic programming
• Sparse dynamic programming I: linear cost functions
• Sequence comparison with mixed convex and concave costs
• Sparse dynamic programming II: convex and concave cost functions