Abstract
A number of data items {1,2,...,n} are to be maintained in a structure
which consists of several linear lists. Successive requests to access
items are independent random variables, and the probability that a
particular request is for item i is p_i. The cost of accessing the
jth item from the front of the list is j. For a single list, the
move-to-front rule (MF) has been extensively studied and has been
shown to provide good performance. In some actual circumstances, MF
is the only physically realizable or convenient policy. We extend the
study of move-to-front by examining the case where items are kept in
several lists. Following its access, an item must be replaced at the
front of one of the lists. In certain cases, assuming the p_is are
known, the policy which minimizes the average retrieval cost takes a
particularly simple form: no item is never moved from the list in
which it is place initially.