to make space for a newly arrived item. The algorithm is charged each time an item is stored or moved to a new location. The goal is to minimize the total number of such moves. The problem is non-trivial for n
In the case that m=Cn for some constant C>1 , there is an algorithm due to Dan Willard (building on work of Itai, Konheim and Rodeh) that stores each item at maximum cost at most O((log(n)^2) per item. In this paper we show that this is optimal (even in the amortized sense): for any algorithm there is a sequence of n items that may require cost Omega(n (log(n)^2 ).
This is joint work with Jan Bulanek and Michal Koucky.