Computationally-optimal real-resource strategies
D. Einav, Michael Fehling · 2002
Managing the cost of deliberation before action in problems where the overall quality of the solution reflects costs incurred and resources consumed in deliberation as well as the cost and benefit of execution, and both the resource consumption in deliberation phase and the costs in deliberation and execution are uncertain and may be described by probability distribution functions, is addressed. A feasible (in terms of resource consumption) strategy that minimizes the expected total cost is termed computationally optimal. For a situation with several independent, uninterruptible methods to solve the problem, a pseudopolynomial-time algorithm that constructs a generate-and-test computationally optimal strategy is developed. This strategy construction problem is shown to be NP-complete, and Bellman's optimality principle is used to solve it efficiently. The results readily extend to the case of multiple resources.>