# Adaptive Caching Networks with Optimality Guarantees

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2016.

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

- [No-Regret Caching via Online Mirror Descent](https://mlsanity.com/paper/2101.12588/) (2021)
- [Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximation](https://mlsanity.com/paper/2202.13187/) (2022)
- [Online Submodular Maximization via Online Convex Optimization](https://mlsanity.com/paper/2309.04339/) (2023)
- [Ascent Similarity Caching with Approximate Indexes](https://mlsanity.com/paper/2107.00957/) (2021)
- [Model Predictive Control is Almost Optimal for Restless Bandit](https://mlsanity.com/paper/2410.06307/) (2024)
- [Efficient and Optimal No-Regret Caching under Partial Observation](https://mlsanity.com/paper/2503.02758/) (2025)
- [Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits](https://mlsanity.com/paper/2511.08097/) (2025)
- [Online Two-Stage Submodular Maximization](https://mlsanity.com/paper/2510.19480/) (2025)

## Abstract (arXiv)

We study the problem of optimal content placement over a network of caches, a problem naturally arising in several networking applications, including ICNs, CDNs, and P2P systems. Given a demand of content request rates and paths followed, we wish to determine the content placement that maximizes the expected caching gain, i.e., the reduction of routing costs due to intermediate caching. The offline version of this problem is NP-hard and, in general, the demand and topology may be a priori unknown. Hence, a distributed, adaptive, constant approximation content placement algorithm is desired. We show that path replication, a simple algorithm frequently encountered in literature, can be arbitrarily suboptimal when combined with traditional eviction policies, like LRU, LFU, or FIFO. We propose a distributed, adaptive algorithm that performs stochastic gradient ascent on a concave relaxation of the expected caching gain, and constructs a probabilistic content placement within 1-1/e factor from the optimal, in expectation. Motivated by our analysis, we also propose a novel greedy eviction policy to be used with path replication, and show through numerical evaluations that both algorithms significantly outperform path replication with traditional eviction policies over a broad array of network topologies.