Incremental versus non-incremental dynamic programming

DOI10.1016/J.ORL.2018.02.003MaRDI QIDQ2417149zbMATH OpenOpenAlexFDO

Authors Stasys Jukna

Publication date 11 June 2019

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2018.02.003

zbMATH Keywords

complexity lower boundsdynamic programmingtropical branching program

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• Limitations of incremental dynamic programming
• Dynamic programming via static incrementalization
• Sorting can exponentially speed up pure dynamic programming
• Greedy can beat pure dynamic programming
• A Comprehensive Model of Dynamic Programming

Cites work

• A Dynamic Programming Approach to Sequencing Problems
• A Theorem on Boolean Matrices
• scientific article; zbMATH DE number 6820278 (Why is no real title available?)
• scientific article; zbMATH DE number 839542 (Why is no real title available?)
• Lower bounds for tropical circuits and dynamic programs
• On a routing problem
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Tropical complexity, Sidon sets, and dynamic programming

Cited in

(1)

• A stochastic model for optimizing crowdfunding campaign success

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Incremental versus non-incremental dynamic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2417149)