  Content delivery networks often employ caching to reduce transmission rates
from the central server to the end users. Recently, the technique of coded
caching was introduced whereby coding in the caches and coded transmission
signals from the central server are considered. Prior results in this area
demonstrate that carefully designing the placement of content in the caches and
designing appropriate coded delivery signals from the server allow for a system
where the delivery rates can be significantly smaller than conventional
schemes. However, matching upper and lower bounds on the transmission rate have
not yet been obtained. In this work, we derive tighter lower bounds on the
coded caching rate than were known previously. We demonstrate that this problem
can equivalently be posed as a combinatorial problem of optimally labeling the
leaves of a directed tree. Our proposed labeling algorithm allows for
significantly improved lower bounds on the coded caching rate. Furthermore, we
study certain structural properties of our algorithm that allow us to
analytically quantify improvements on the rate lower bound for general values
of the problem parameters. This allows us to obtain a multiplicative gap of at
most four between the achievable rate and our lower bound.
