Tata Institute of Fundamental Research
An Optimal Lower Bound for File Maintenance
Seminar
Organiser:
John Barretto
Date:
Friday, 13 Jan 2012, 11:30 to 12:30
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
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 rm 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 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).
| Organiser: | John Barretto |
| Date: | Friday, 13 Jan 2012, 11:30 to 12:30 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
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 rm 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 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).