Finite-State Processes and Dynamic Programming
Authors:
- Richard M. KarpRKRichard M. Karp
- Michael HeldMHMichael Held
- 1 May 1967
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Applied Mathematics
- Vol. 15 (3) , 693-718
Abstract
This paper develops a formalism within which the application of dynamic programming to discrete, deterministic problems is rigorously studied. The two central concepts underlying this development are discrete decision process and sequential decision process. Discrete decision processes provide a convenient means of problem statement, while monotone sequential decision processes (which are finite automata with a certain cost structure superimposed) correspond naturally to dynamic programming algorithms. The representations of discrete decision processes by monotone sequential decision processes are characterized, and this characterization is used in the deviation of dynamic programming algorithms for a variety of problems.Keywords
This publication has 13 references indexed in Scilit:
- Discounted Dynamic ProgrammingThe Annals of Mathematical Statistics, 1965
- Composition Principles for Synthesis of Optimal Multistage ProcessesOperations Research, 1964
- Assembly-Line Balancing—Dynamic Programming with Precedence ConstraintsOperations Research, 1963
- Applied Dynamic Programming1962
- A Dynamic Programming Approach to Sequencing ProblemsJournal of the Society for Industrial and Applied Mathematics, 1962
- A Linear Programming Approach to the Cutting-Stock ProblemOperations Research, 1961
- Combinatorial processes and dynamic programming1960
- The Truck Dispatching ProblemManagement Science, 1959
- On a routing problemQuarterly of Applied Mathematics, 1958
- Discrete-Variable Extremum ProblemsOperations Research, 1957