Limitations of incremental dynamic programming

DOI10.1007/s00453-013-9747-6zbMath1360.90269OpenAlexW1978018612MaRDI QIDQ517805

Stasys P. Jukna

Publication date: 27 March 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9747-6

zbMATH Keywords

dynamic programmingmatchinglower boundsknapsackbranching programs

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorial optimization (90C27) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (3)

On pure space vs catalytic space ⋮ Sufficient and necessary conditions for solution finding in valuation-based systems ⋮ On pure space vs catalytic space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Toward a model for backtracking and dynamic programming
• A stronger model of dynamic programming algorithms
• 35/44-approximation for asymmetric maximum TSP with triangle inequality
• Boolean function complexity. Advances and frontiers.
• Models of greedy algorithms for graph problems
• A nondeterministic space-time tradeoff for linear codes
• Priority algorithms for graph optimization problems
• Neither reading few bits twice nor reading illegally helps much
• (Incremental) priority algorithms
• Priority algorithms for makespan minimization in the subset model.
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• The power of priority algorithms for facility location and set cover
• On lower bounds for read-\(k\)-times branching programs
• Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems
• Efficient determination of the transitive closure of a directed graph
• Bounds on Greedy Algorithms for MAX SAT
• Proof verification and the hardness of approximation problems
• A Dynamic Programming Approach to Sequencing Problems
• Time-space trade-off lower bounds for randomized computation of decision problems
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• A Comprehensive Model of Dynamic Programming
• A common schema for dynamic programming and branch and bound algorithms
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• `` Strong NP-Completeness Results
• A note on read-$k$ times branching programs
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• Branching Programs and Binary Decision Diagrams
• Finite-State Processes and Dynamic Programming

This page was built for publication: Limitations of incremental dynamic programming