Nonserial dynamic programming: On the optimal strategy of variable elimination for the rectangular lattice

AbstractThe secondary optimization problem in dynamic programming consists of finding the “best” order of variable elimination. This problem can be completely stated in terms of an “interaction graph” representing the variable interaction structure of the objective function. In this paper, two general results about the variable elimination process are presented.The class of problems having a rectangular lattice as interaction graph is then considered in detail, and two particular variable elimination strategies are both proved optimal. An application to picture processing by computer is finally shown. The same interaction graph, but with a different cost function, is also suitable for representing the topological structure of a (sparse) symmetric system of linear algebraic equations. Here the problem is to find the order of Gaussian elimination of the variables yielding the minimal number of multiplications. The results of this paper apply also partially to this type of variable elimination process