Finite State Representations of Discrete Optimization Problems
Toshihide Ibaraki · SIAM Journal on Computing · 1973
This paper is concerned with the representation of a discrete optimization problem given in the form of a $ddp$ (discrete decision process) by a G-$sdp$ (G-sequential decision process). A G-$sdp$ is a finite state model of discrete optimization problem, consisting of a finite number of states and a rule specifying the transition from one state to another corresponding to each decision applied to it. A cost function, taken from a given family of functions G, is associated with each transition. A necessary and sufficient condition for a given $ddp$ to be represented by a G-$sdp$, which is valid for most important G’s, is obtained ; it turns out that various representation theorems obtained in the earlier paper [3] are special cases of this theorem. Furthermore, a case in which the existence of the unique minimal representation is guaranteed to exist receives special attention, and some sufficient conditions are discussed.