BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/242
DTSTAMP:20230914T125916Z
SUMMARY:An Optimal Lower Bound for File Maintenance
DESCRIPTION:Speaker: \n\nAbstract: \nIn the file maintenance problem\, n in
teger 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 consecutiv
e 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 s
pace 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 nu
mber of such moves. The problem is non-trivial for n 1\, there is an algor
ithm due to Dan Willard (building on work of Itai\, Konheim and Rodeh) tha
t 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 (lo
g(n)^2) (this is joint work with Jan Bulanek and Michal Koucky).\n
URL:https://www.tcs.tifr.res.in/web/events/242
DTSTART;TZID=Asia/Kolkata:20120113T113000
DTEND;TZID=Asia/Kolkata:20120113T123000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR