Further results on lower bounds for coded caching
Hooshang Ghasemi, Aditya Ramamoorthy · 2016
Coded caching is a technique that promises huge rate savings in certain canonical content distribution scenarios over the Internet. In the coded caching setting, previous contributions have demonstrated a constant multiplicative gap between the achievable rate and corresponding lower bound on the rate, independent of the problem parameters. Our prior work demonstrated that good lower bounds on the coded caching rate can be obtained by equivalently considering a combinatorial problem on a directed tree. In this work, we study certain structural properties of our algorithm that allow us to analytically quantify improvements on the rate lower bound. This analysis allows us to obtain a multiplicative gap of at most four between the achievable rate and our lower bound. To our best knowledge, this is the best known multiplicative gap known for this problem.