A stronger model of dynamic programming algorithms
From MaRDI portal
Publication:547305
DOI10.1007/s00453-009-9385-1zbMath1220.90155OpenAlexW2151669659MaRDI QIDQ547305
Russell Impagliazzo, Joshua Buresh-Oppenheim, Sashka Davis
Publication date: 1 July 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-009-9385-1
Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (8)
A general framework for enumerating equivalence classes of solutions ⋮ Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems ⋮ Toward a model for backtracking and dynamic programming ⋮ Yet harder knapsack problems ⋮ Limitations of incremental dynamic programming ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ Sufficient and necessary conditions for solution finding in valuation-based systems ⋮ Computing (and Life) Is All about Tradeoffs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Toward a model for backtracking and dynamic programming
- Scheduling jobs with fixed start and end times
- (Incremental) priority algorithms
- Priority algorithms for makespan minimization in the subset model.
- The power of priority algorithms for facility location and set cover
- Dynamic programming and stochastic control processes
- A Comprehensive Model of Dynamic Programming
- Algorithms for maximum independent sets
- A common schema for dynamic programming and branch and bound algorithms
- Hard Knapsack Problems
- Dynamic Programming is Optimal for Nonserial Optimization Problems
- On Syntactic versus Computational Views of Approximability
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
- Finite-State Processes and Dynamic Programming
- Approximation and Online Algorithms
- Automata, Languages and Programming
This page was built for publication: A stronger model of dynamic programming algorithms
