A linear-time algorithm for concave one-dimensional dynamic programming
From MaRDI portal
Publication:909460
DOI10.1016/0020-0190(90)90215-JzbMath0694.68032WikidataQ29300501 ScholiaQ29300501MaRDI QIDQ909460
Publication date: 1990
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items
A note on the traveling repairman problem ⋮ Strongly polynomial efficient approximation scheme for segmentation ⋮ Efficient algorithms for centers and medians in interval and circular-arc graphs ⋮ Online dynamic programming speedups ⋮ Selection and sorting in totally monotone arrays ⋮ Approximate regular expression pattern matching with concave gap penalties ⋮ Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon ⋮ Structured \(p\)-facility location problems on the line solvable in polynomial time ⋮ Perspectives of Monge properties in optimization ⋮ Consecutive interval query and dynamic programming on intervals ⋮ Minimum \(L_k\) path partitioning-an illustration of the Monge property ⋮ Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane ⋮ A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time ⋮ Dynamic programming with convexity, concavity and sparsity ⋮ New algorithms for facility location problems on the real line ⋮ A dynamic programming approach of finding an optimal broadcast schedule in minimizing total flow time ⋮ Speeding up dynamic programming in the line-constrained \(k\)-median ⋮ Speeding up Dynamic Programming in the Line-Constrained k-median ⋮ Sparse LCS common substring alignment ⋮ Locating stops along bus or railway lines -- a bicriteria problem
Cites Work
- Unnamed Item
- Geometric applications of a matrix-searching algorithm
- Speeding up dynamic programming with applications to molecular biology
- Sequence comparison with mixed convex and concave costs
- The Least Weight Subsequence Problem
- The concave least-weight subsequence problem revisited
- Speed-Up in Dynamic Programming
