BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T234616Z
UID:Seminar-dept-1079@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20231128T130000
DTEND:20231128T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Sharat Ibrahimpur: Efficient Caching with Reserves via Marking\n\nOnline caching is among the most fundamental and well-studied problems in the area of online algorithms. Much of traditional caching research studies cache management for a single-user or single-processor environment. In this work, we introduce and study a model of caching that captures issues that arise in a multi-user environment. In the caching with reserves problem, we have m users sharing a cache that can hold k pages and we are given a reserve requirement k_i for each user i. Page requests arrive online and the goal is to dynamically maintain the cache so that the number of cache misses is minimized while ensuring that the cache holds at least k_i pages belonging to user i at any time. \n\n\n\nUnlike the classical setting, the caching with reserves problem is NP-hard even in the offline setting, where the page sequence is known in advance. Here, we give an offline 2-approximation algorithm that is inspired by Belady's farthest-in-the-future rule. In the online setting, we show that a water-filling strategy gives an O(log k)-competitive fractional algorithm, and this can be further turned into a marking-style randomized integral algorithm at a constant factor loss in competitiveness. Our competitive analysis has two main ingredients. We use a simple potential function to upper bound the number of cache misses incurred by the fractional algorithm. Complementing this, we give a novel LP dual-fitting based lower bound on the number of cache misses incurred by any offline algorithm.\n\n\n\nJoint work with Manish Purohit, Zoya Svitkina, Erik Vee, and Joshua Wang.\n\n\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1079
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR