Optimal List Order under Partial Memory Constraints.
Abstract
The problem of interest is to determine the optimal ordering so as to minimize the long run average cost. Clearly if the P sub i were known the optimal ordering would simply be to order the elements in decreasing order of the P sub i's. In fact even if the P sub i's were unknown we could do as well asymptotically by ordering the elements at each unit of time in decreasing order of the number of previous requests for them. In this paper we first consider the case in which the only memory allowed at any time is the ordering of the elements at that time; in other words, the only type of reordering rules we allow are ones in which the reordered permutation of elements at any time is only allowed to depend on the present ordering and the position of the element requested. We also consider the above problem under the previse that additional memory is allowed. In particular we allow the decision-maker to utilize such rules as 'only make a change (according to some preassigned rule) if the same element has been requested k times in a row.' We show that as k approaches infinity we can do as well as if we knew the values of the P sub i, and in addition we show that the convergence is monotone.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1979
- Accession Number
- ADA077139
Entities
People
- Sheldon M. Ross
- Yi C. Kan
Organizations
- University of California, Berkeley