A counterexample to a conjecture in optimal list ordering

E.J. Anderson, P. Nash, and R.R. Weber, J. Appl. Prob. 19(9) 730-732, 1982.

Abstract

A number of items are arranged in a line.  At each unit of time one of the items 
is requested, the $i$th being requested with probability $P_i$.  We consider 
rules which reorder the items between successive requests in a fashion which 
depends only on the position in which the most recently requested item was 
found. It has been conjectured that the rule which always moves the requested 
item to the front of the line minimizes the average position of the requested 
item.  An example with six items shows that this conjecture is false.  

back to list of papers