Dynamic Programming is Optimal for Nonserial Optimization Problems

DOI10.1137/0211004zbMath0479.90081OpenAlexW2076776753MaRDI QIDQ3937164

Arnon Rosenthal

Publication date: 1982

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0211004

zbMATH Keywords

discrete optimizationexponential lower boundBellman's principle of optimalitynonserial dynamic programminglimited form of decompositionnonoverlapping comparison algorithmsperfect elimination graph

Mathematics Subject Classification ID

Dynamic programming (90C39)

Related Items

The principle of optimality in the design of efficient algorithms, Systolic processing for dynamic programming problems, Nonserial dynamic programming formulations of satisfiability, Linear time algorithms for NP-hard problems restricted to partial k- trees, Dynamic programming is optimal for certain sequential decision processes, A stronger model of dynamic programming algorithms, Exact algorithms for the Hamiltonian cycle problem in planar graphs, Power indices and easier hard problems, A Comprehensive Model of Dynamic Programming, Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey