  A centralized coded caching scheme has been proposed by Maddah-Ali and Niesen
to reduce the worst-case load of a network consisting of a server with access
to N files and connected through a shared link to K users, each equipped with a
cache of size M. However, this centralized coded caching scheme is not able to
take advantage of a non-uniform, possibly very skewed, file popularity
distribution. In this work, we consider the same network setting but aim to
reduce the average load under an arbitrary (known) file popularity
distribution. First, we consider a class of centralized coded caching schemes
utilizing general uncoded placement and a specific coded delivery strategy,
which are specified by a general file partition parameter. Then, we formulate
the coded caching design optimization problem over the considered class of
schemes with 2^K2^N variables to minimize the average load by optimizing the
file partition parameter under an arbitrary file popularity. Furthermore, we
show that the optimization problem is convex, and the resulting optimal
solution generally improves upon known schemes. Next, we analyze structural
properties of the optimization problem to obtain design insights and reduce the
complexity. Specifically, we obtain an equivalent linear optimization problem
with (K+1)N variables under an arbitrary file popularity and an equivalent
linear optimization problem with K+1 variables under the uniform file
popularity. Under the uniform file popularity, we also obtain the closed form
optimal solution, which corresponds to Maddah-Ali-Niesen's centralized coded
caching scheme. Finally, we present an information-theoretic converse bound on
the average load under an arbitrary file popularity.
