Dynamic programming to minimize the maximum number of open stacks

Abstract

We give a dynamic-programming solution to the problem of minimizing the maximum number of open stacks. Starting from a call-based dynamic program, we show a number of ways to improve the dynamic- programming search, preprocess the problem to simplify it, and determine lower and upper bounds. We then explore a number of search strategies for reducing the search space. The final dynamic-programming solution is, we believe, highly effective. © 2007 INFORMS.