Oct 18, 3:30pm, GHC 4405

Michael Saks, Rutgers

An optimal lower bound for file maintenance

Michael Saks, Rutgers

An optimal lower bound for file maintenance

Abstract:

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 talk I'll discuss recent work of Jan Bulanek, Michal Koucky and myself proving a matching lower bound.