An Optimal Lower Bound for File Maintenance

In the file maintenance problem, n integer items from the set {1,....,r} are to be stored in an array of size m>=n . The items are presented sequentially in an arbitrary order and must be stored in the array in sorted order (but not necessarily in consecutive locations in the array). Each new item is stored before the next arrives. If r=m then we can simply store item j in location j , but if r>m then we may have to shift the location of stored items IN 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 = m r . 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.