A linear-time algorithm for concave one-dimensional dynamic programming

DOI10.1016/0020-0190(90)90215-JzbMath0694.68032DBLPjournals/ipl/GalilP90WikidataQ29300501 ScholiaQ29300501MaRDI QIDQ909460

Zvi Galil, Kun Soo Park

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

dynamic programmingquadrangle inequalitytotal monotonicity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39)

Related Items (20)

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

This page was built for publication: A linear-time algorithm for concave one-dimensional dynamic programming