We consider discrete optimization problems in which the only exploitable feature of the objective function is a limited form of decomposability. “Nonoverlapping comparison algorithms” are defined as a model of procedures which decompose the problem and apply Bellman’s principle of optimality. Nonserial dynamic programming (DP), a simple elimination procedure, is shown to be optimal among all nonoverlapping comparison algorithms, including nondeterministic algorithms. These results can give an exponential lower bound on the shortest admissible proof that a solution is optimal. Furthermore, if part of the search space is ruled out, a subset of the comparisons made by DP optimally searches the remainder. We suggest that the running time of DP is a useful measure of the “interaction complexity” of a problem, and that because of its simplicity DP is of practical as well as theoretical interest.

In this paper, we consider the accessing of batched requests in a linear storage medium. The batch size is assumed fixed and the access probabilities of individual records known. For a given arrangement of records in the storage, we consider the problem of read/write head scheduling to minimize the expected access time for a batch measured in terms of the distance traveled by the head. In the first part of the paper, several simple algorithms are proposed, analyzed and compared. The effect of different record arrangements is also discussed. In the second part of the paper, a family of algorithms called B-optimal rules are described. When B is $\infty$, an Batched processing   expected access time   read/write head scheduling   minimization of disk seek time   linear storage medium   near-optimal algorithms   optimal algorithms   scheduling algorithms   -optimal algorithms   -optimal algorithms   organ-pipe arrangement of records   discrete dynamic programming