A stronger model of dynamic programming algorithms

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

zbMATH Keywords

dynamic programmingpriority algorithmsalgorithmic paradigms

Mathematics Subject Classification ID

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