# Kelly Cache Networks

arXiv: https://arxiv.org/abs/1901.04092 · HTML: https://mlsanity.com/paper/1901.04092/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jan 2019.

## Built on by (most cited first, 3 of 3)

- [Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximation](https://mlsanity.com/paper/2202.13187/) (2022)
- [Submodular Maximization via Taylor Series Approximation](https://mlsanity.com/paper/2101.07423/) (2021)
- [Stochastic Submodular Maximization via Polynomial Estimators](https://mlsanity.com/paper/2303.09960/) (2023)

## Abstract (arXiv)

We study networks of M/M/1 queues in which nodes act as caches that store objects. Exogenous requests for objects are routed towards nodes that store them; as a result, object traffic in the network is determined not only by demand but, crucially, by where objects are cached. We determine how to place objects in caches to attain a certain design objective, such as, e.g., minimizing network congestion or retrieval delays. We show that for a broad class of objectives, including minimizing both the expected network delay and the sum of network queue lengths, this optimization problem can be cast as an NP- hard submodular maximization problem. We show that so-called continuous greedy algorithm attains a ratio arbitrarily close to 1 - 1/e ≈ 0.63 using a deterministic estimation via a power series; this drastically reduces execution time over prior art, which resorts to sampling. Finally, we show that our results generalize, beyond M/M/1 queues, to networks of M/M/k and symmetric M/D/1 queues.