Elastic caching

Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi

Research output: Contribution to conferencePaperpeer-review


Motivated by applications in cloud computing, we study the classical online caching problem for a cache of variable size, where the algorithm pays a maintenance cost that monotonically increases with cache size. This captures not only the classical setting of a fixed cache size, which corresponds to a maintenance cost of 0 for a cache of size at most k and ∞ otherwise, but also other natural settings in the context of cloud computing such as a concave rental cost on cache size. We call this the elastic caching problem. Our results are: (a) a randomized algorithm with a competitive ratio of O(log n) for maintenance cost that is an arbitrary function of cache size, (b) a deterministic algorithm with a competitive ratio of 2 for concave, or more generally submodular maintenance costs, (c) a deterministic n-competitive algorithm when the cost function is any monotone non-negative set function, and (d) a randomized constant-factor approximation algorithm for the offline version of the problem. Our algorithms are based on a configuration LP formulation of the problem, for which our main technical contribution is to maintain online a feasible fractional solution that can be converted to an integer solution using existing rounding techniques.

Original languageEnglish (US)
Number of pages14
StatePublished - 2019
Event30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States
Duration: Jan 6 2019Jan 9 2019


Conference30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
Country/TerritoryUnited States
CitySan Diego

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Elastic caching'. Together they form a unique fingerprint.

Cite this