### DIMACS Theoretical Computer Science Seminar

Title: An optimal lower bound for file maintenance

Speaker: **Michael Saks**, Rutgers University

Date: Wednesday, February 8, 2012 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

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 itemsIN
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.

See: http://paul.rutgers.edu/~yixinxu/theory-spring12.html