Department Seminar Series

Efficient Caching with Reserves via Marking

28th November 2023, 13:00 add to calenderAshton Lecture Theatre
Dr. Sharat Ibrahimpur
Department of Mathematics, London School of Economics and Political Science

Abstract

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

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

Joint work with Manish Purohit, Zoya Svitkina, Erik Vee, and Joshua Wang.

add to calender (including abstract)

Biography

Sharat Ibrahimpur is a Research Officer in Algorithms and Optimisation at the London School of Economics and Political Science. Before arriving in the UK, he obtained his masters and PhD degrees in Combinatorics and Optimization from the University of Waterloo in Canada. He was advised by Dr. Chaitanya Swamy during this time and his PhD thesis is on designing approximation algorithms for some stochastic optimization problems with norm-based objective functions. Going further back, Sharat’s undergraduate degree was in Applied Mathematics from the Indian Institute of Technology Roorkee in India.

Additional Materials