Optimal Coded Multicast in Cache Networks with Arbitrary Content Placement
Seyed Mohammad Asghari, Yi Ouyang, Ashutosh Nayyar, A. Salman Avestimehr · 2018
A new class of caching schemes, called coded caching, can significantly reduce the communication bandwidth requirement for satisfying users' demands by utilizing the multicasting gain among multiple users. Most existing works assume that the users follow the prescriptions for content placement made by the system. However, users may prefer to decide what files to cache or discard some part of their caches due to lack of space. In order to address this issue, we study a caching system where the content placement phase has been already carried out by the users arbitrarily. More specifically, we consider a network consisting of a file server connected through a shared link to $K$ users, each equipped with a cache. Given arbitrary content placement by the users, the goal is to find a coded multicast strategy for the server that minimizes the load of the shared link. We first formulate the optimal coded multicast design problem as an Integer Linear Program (ILP). Using a connection with the weighted set cover problem, we propose an approximation algorithm for solving this problem. We show that our proposed algorithm provides $(1 + \log K)$-approximation for the optimal coded multicast design problem, while the approximation ratio for the existing coded delivery schemes is linear in $K$. Numerical simulations show that our proposed algorithm provides a considerable bandwidth reduction over the existing coded delivery schemes for uniformly-random generated content placement.