Minimum cost caching-aided multicast under arbitrary demand

We address the content distribution problem as a network information flow problem on a caching augmented graph for which we provide a linear programming (LP)-based information theoretical lower bound. We show that while the LP solution involves high exponential complexity, the structure of the caching and transport configuration problems can be exploited to provide a set of solutions that tradeoff complexity with optimality. In particular, we show that while polynomial-time delivery schemes that employ random linear-coded transmission along with uncoded popularity-based caching are order-optimal under heavy tail Zipf popularity distributions, when the Zipf parameter decreases, the use of uncoded popularity-based vector caching can maintain constant-to-optimal performance at the expense of exponential-time network-coded transmission schemes that create multicasting opportunities even for users requesting distinct subsets of content objects.