{'fraction_non_alphanumeric': 0.051870283276823796, 'fraction_numerical': 0.012523241824346495, 'mean_word_length': 4.218005421600799, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Structural Properties of Uncoded Placement Optimization for Coded Delivery

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.


I. INTRODUCTION
To support the dramatic growth of wireless data traffic, caching and multicasting have been proposed as two promising approaches for massive content delivery in wireless networks. By proactively placing content closer to or even at end-users during the off-peak hours, network congestion during the peak hours can be greatly reduced. On the other hand, leveraging the broadcast nature of the wireless medium by multicast transmission, popular content can be delivered to multiple requesters simultaneously. Recently, a new class of caching schemes for content placement in user caches, referred to as coded caching [1]- [12], which jointly consider caching and multicasting, have received significant interest. The main novelty of such schemes with respect to (w.r.t.) conventional approaches (e.g., as currently used in content delivery networks) is that the messages stored in the user caches are treated as "receiver side information" in order to enable network-coded multicasting, such that a single multicast codeword is useful to a large number of users, even though they are not requesting the same content. In [1] and [2], Maddah-Ali and Niesen consider a system with one server connected through a shared error-free link to K users. The server has a library of N files (of the same length), and each user has an isolated cache memory of M files. They formulate a caching problem, consisting of two phases, i.e., uncoded content placement and coded content delivery, which has been successively investigated in a large number of recent works [3]- [12] under the same network setting.
In [1]- [5], the goal is to reduce the worst-case (over all possible requests) load 1 of the shared link in the delivery phase. In particular, in [1], Maddah-Ali and Niesen propose a centralized coded caching scheme, which requires knowledge of the number of active users in the delivery phase, and achieves order-optimal memory-load tradeoff. It is successively shown in [10] that Maddah-Ali-Niesen's centralized coded caching scheme [1] achieves the minimum worst-case load under uncoded placement and N ≥ K. Motivated by [1], decentralized coded caching schemes are proposed in [2] and [3], where the number of active users in the system are not known in the placement phases and the schemes can achieve order-optimal memory-load tradeoff in the asymptotic regime of infinite file size (i.e., the number of data units per file goes to infinity).
In the finite file size regime, Maddah-Ali-Niesen's decentralized coded caching scheme [2] is 1 For future reference, in this paper, we refer to "load" of a particular coded caching scheme as the ratio of the length of the coded multicast message over the length of a single library file.
shown to achieve an undesirable worst-case load [4], which is larger than the worst-case load achieved by the decentralized scheme that we present in [3]. In [5], Yu et al. propose a centralized coded caching scheme to reduce the average load under the uniform file popularity, by efficiently serving users with common requests. Note that all the coded caching schemes in [1]- [3], [5] dedicate the same fraction of memory to each file, and may not be able to take full advantage of a non-uniform, possibly very skewed, popularity distribution.
In [6]- [9], the goal is to reduce the average load of the shared link in the delivery phase under an arbitrary file popularity. Specifically, in [6], the authors partition files into multiple groups and apply Maddah-Ali-Niesen's decentralized coded caching scheme [2] to each group.
As coded-multicasting opportunities for files from different groups are not fully explored, it is expected that the average load in [6] can be further reduced. In [7], a decentralized coded caching scheme where the memory allocation for files with different popularity is optimized using an upper bound on the average load is proposed. However, such optimization is highly non-convex and not amenable to analysis. Therefore, a simpler but suboptimal scheme (referred to as the RLFU-GCC decentralized coded caching scheme) where the library is partitioned only into two groups, is also proposed for the purpose of asymptotic analysis, and some optimality properties in the scaling laws of the average load versus the system parameters are obtained analytically, in particular for the case of a Zipf popularity distribution. In [8], inspired by the RLFU-GCC decentralized coded caching scheme in [7], Zhang et al. present a similar coded caching scheme which partitions the library into two groups and show that the achieved average load is within a constant factor of the minimum average load over all possible schemes under an arbitrary file popularity (except a small additive term) in the general regimes of the system parameters. In [9], Wang et al. formulate a coded caching design problem to minimize the average load by optimizing the cache memory for storing each file. To reduce the computational complexity, Wang et al. consider a simplified objective function, i.e., the total average size of the uncached files and obtain a sub-optimal solution, which is shown to be order-optimal when the number of users and the number of files are large, assuming that the file popularity follows a Zipf distribution. However, in the general regime, there is no performance guarantee for the sub-optimal solution.
Besides achievable schemes, [5]- [9], [11]- [13] present information-theoretic converse bounds for coded caching. The bounds in [5]- [9], [11]- [13] can be classified into two classes, i.e., class i): bounds that are only suitable for uncoded placement and class ii): bounds that are suitable for any placement including uncoded placement and coded placement. The bound in [5] belongs to class i) and is exactly tight, for both the worst-case load and the average load (under the uniform file popularity). The bounds based on reduction from an arbitrary file popularity to the uniform file popularity [6]- [8], cut-set [9], relation between a multi-user single-request caching network and a single-user multi-request caching network [12], and other informationtheoretic approaches [11], [13], belong to class ii). In particular, the bound in [13] is tighter than other bounds under the uniform file popularity, but it is rather complicated and cannot be applied directly to the case of non-uniform file popularity as the bounds in [6]- [9], [12]. However, the bounds in [6]- [9], [12] for an arbitrary popularity distribution are not generally tight in nonasymptotic regimes of the system parameters. Thus, it is important to obtain a tighter converse bound on the average load under an arbitrary file popularity in non-asymptotic regimes of the system parameters.
In this paper, we consider the same problem setting as in [1]. To obtain first-order design insights, we focus on investigating centralized coded caching schemes to minimize the average load under an arbitrary popularity distribution, which may later motivate efficient designs of decentralized coded caching schemes. Our main contributions are summarized below.
• 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. This class of centralized coded caching schemes include Maddah-Ali-Niesen's centralized coded caching scheme [1], each realization of Maddah-Ali-Niesen's decentralized (random) coded caching scheme [2] and each realization of Zhang et al.'s decentralized (random) coded caching scheme [8].
• We formulate the coded caching design optimization problem over the considered class of schemes with 2 K ·N K variables to minimize the average load by optimizing the file partition parameter under an arbitrary file popularity. Contrary to the optimization in [7] which is non-convex and is difficult to analyze, we show that the proposed optimization problem is convex and amenable to analysis. Furthermore, we show that the resulting optimized average load is generally better than those of upon known schemes and the linear coded delivery procedures of the considered class of schemes have the same performance as the graph-coloring index coding delivery procedure in [7], called the GCC 1 procedure and the delivery procedure which adopts an appending method to avoid the "bit waste" problem in [14], called the HCD procedure, when applied to the optimized file placement parameter.
• We analyze structural properties of the optimization problem to obtain design insights and reduce the complexity for obtaining an optimal solution. Specifically, we obtain an equivalent linear optimization problem with (K + 1)N variables. To further reduce the complexity of the linear optimization problem under the uniform file popularity, we obtain an equivalent linear optimization problem with K + 1 variables. We also obtain the closed-form optimal solution under the uniform file popularity for all M ∈ {0, N K , 2N K , . . . , N}. This optimal solution corresponds to Maddah-Ali-Niesen's centralized coded caching scheme [1], aiming at reducing the worst-case load.
• We present a genie-aided converse bound on the average load under an arbitrary file popularity using the genie-aided approach proposed in [7]. When the file popularity is uniform, the genie-aided converse bound reduces to the converse bound on the average load under the uniform file popularity derived in [11].
• Numerical results verify the analytical results and demonstrate the promising performance of the optimized parameter-based scheme. Numerical results also show that the presented genie-aided converse bound is tighter than the converse bounds in [7], [8] for any cache size and is tighter than the converse bounds in [9], [12] when the cache size is modest or large.

II. PROBLEM SETTING
As in [1], [3], we consider a system with one server connected through a shared error-free link to K ∈ N users, where N denotes the set of all natural numbers. 2 The server has access to a library of N ∈ N files, denoted by W 1 , . . . , W N , each consisting of F ∈ N indivisible data units. Let N {1, 2, . . . , N} and K {1, 2, . . . K} denote the set of file indices and the set of user indices, respectively. Different from [1], we assume that each user randomly and independently requests a file in N according to an arbitrary file popularity. In particular, a user requests W n with probability p n ∈ [0, 1], where n ∈ N . Thus, the file popularity distribution is 2 The problem setting is similar to the one we presented in [3], expect that here we consider an arbitrary file popularity and focus on minimizing the average load.
given by p (p n ) N n=1 , where N n=1 p n = 1. In addition, without loss of generality, we assume p 1 ≥ p 2 ≥ . . . ≥ p N . Each user has an isolated cache memory of MF data units, for some real number M ∈ [0, N].
The system operates in two phases, i.e., a placement phase and a delivery phase [1]. In the placement phase, the users are given access to the entire library of N files. Each user is then able to fill the content of its cache using the library. Let φ k denote the caching function for user k, which maps the files W 1 , . . . , W N into the cache content Z k φ k (W 1 , . . . , W N ) for user k ∈ K. Let φ (φ 1 , . . . , φ K ) denote the caching functions of all the K users. Note that Z k is of size MF data units. Let Z (Z 1 , · · · , Z K ) denote the cache contents of all the K users. In the delivery phase, each user randomly and independently requests one file in N according to file popularity distribution p. Let D k ∈ N denote the index of the file requested by user k ∈ K, and let D (D 1 , · · · , D K ) ∈ N K denote the requests of all the K users. The server replies to these K requests by sending a message over the shared link, which is observed by all the K users. Let ψ denote the encoding function for the server, which maps the files W 1 , . . . , W N , the cache contents Z, and the requests D into the multicast message Y ψ(W 1 , . . . , W N , Z, D) sent by the server over the shared link. Let µ k denote the decoding function for user k, which maps the multicast message Y received over the shared link, the cache content Z k and the request D k , to the estimate W D k µ k (Y, Z k , D k ) of the requested file W D k of user k ∈ K. Let µ (µ 1 , . . . , µ K ) denote the decoding functions of all the K users. Each user should be able to recover its requested file from the message received over the shared link and its cache content.
Thus, we impose the successful content delivery condition Given the cache size M, the cache contents Z and the requests D of all the K users, let  denote the average (normalized) load of the shared link, where the average is taken over requests denote the minimum average (normalized) load of the shared link. In this paper, we adopt a specific delivery strategy (i.e., the encoding function ψ) and decoding functions µ. Based on these, we wish to minimize the average load of the shared link in the delivery phase under successful content delivery condition, by optimizing the placement strategy (i.e., the caching functions φ) of uncoded placement. As in [1], in this paper we focus on studying effective centralized coded caching schemes to obtain first-order design insights. The obtained results can be extended to design efficient decentralized coded caching schemes, e.g., using the methodology we propose in [3]. However, the detailed investigation of possible decentralized schemes inspired by the centralized approach of this paper is left for future work.

III. CENTRALIZED CODED CACHING SCHEME
In this section, we first present 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 show that the class of centralized coded caching schemes include the schemes in [1], [2], [8].

A. Parameter-based Centralized Coded Caching
In the uncoded placement phase, each file is partitioned into 2 K nonoverlapping subfiles. We label the subfiles of file W n as W n = (W n,S : S ⊆ K), where subfile W n,S represents the data units of file n stored in the cache of the users in set S. We say subfile W n,S is of type s if |S| = s [14]. Thus, the cache content at user k is given by Let x n,S denote the ratio between the number of data units in W n,S and the number of data units in W n (i.e., F ). Let x (x n,S ) n∈N ,S⊆K denote the file partition parameter. Each specific choice of the file partition parameter x corresponds to one centralized coded caching scheme within 3 Later, we shall use slightly different notations for the average load to reflect the dependency on the specific scheme considered.
the considered class. This parameter is a design parameter and will be optimized to minimize the average load in Section IV. Thus, x satisfies K s=0 S∈{S⊆K:|S|=s} N n=1 K s=1 S∈{S⊆K:|S|=s,k∈S} where (3) represents the file partition constraint and (4) represents the cache memory constraint.
In the coded delivery phase, the K users are served simultaneously using coded-multicasting.
Consider any s ∈ {1, 2, . . . , K}. We focus on a subset of users S ⊆ K with |S| = s. Observe that every s − 1 users in S share a subfile that is needed by the remaining user in S. More precisely, for any k ∈ S, the subfile W D k ,S\{k} is requested by the user storing cache content k, since it is is present in the cache of any user in S \ {k}. For any subset S of cardinality |S| = s, the server transmits coded multicast message ⊕ k∈S W D k ,S\{k} , where ⊕ denotes bitwise XOR. All subfiles in the coded multicast message are assumed to be zero-padded to the length of the longest subfile.
For all s ∈ {1, 2, . . . , K}, we conduct the above delivery procedure. The multicast message Y is simply the concatenation of the coded multicast messages for all s ∈ {1, 2, . . . , K}.
Finally, we formally summarize the placement and delivery procedures of the class of the centralized coded caching schemes specified by the general file partition parameter x in Algorithm 1.

B. Relations with Existing Schemes
We discuss the relation between the class of the centralized coded caching schemes in Algorithm 1 and Maddah-Ali-Niesen's centralized [1] and decentralized [2] for S ⊆ K : |S| = s do Next, we compare the delivery procedures of the five schemes. The delivery procedure of Algorithm 1 is the same as the delivery procedure of Maddah-Ali-Niesen's decentralized coded caching scheme and is designed for types 0, 1, . . . , K. In contrast, the delivery procedure of Maddah-Ali-Niesen's centralized coded caching scheme is designed only for type KM N , and the delivery procedure of Zhang et al.'s decentralized coded caching scheme is designed for types 0, 1, . . . , K, where K ∈ {0, 1, . . . , K} is a random variable. Note that the delivery procedures of the above four coded caching schemes are linear coded delivery procedures. The delivery procedure of the RLFU-GCC decentralized coded caching scheme adopts a graph-coloring index coding delivery procedure designed for types 0, 1, . . . , K, called the GCC 1 procedure.
The discussion of the relation with the GCC 1 procedure is deferred to the end of Section IV-A.

IV. AVERAGE LOAD MINIMIZATION
In this section, we first formulate the coded caching design optimization problem over the considered class of schemes to minimize the average load under an arbitrary file popularity.
Then, we analyze structural properties of the optimization problem to obtain design insights and reduce the complexity for obtaining an optimal solution.

A. Problem Formulation
Consider the class of the centralized coded caching schemes specified by the general file partition parameter x in Algorithm 1. Denote R(K, N, M, x, D) as the load for serving the K users with cache size M under given file partition parameter x and requests D. By Algorithm 1, we have where The file partition parameter x fundamentally affects the average load R avg (K, N, M, x). We would like to minimize R avg (K, N, M, x) by optimizing x, under the constraints on x in (2), (3) and (4).

Problem 1 (File Partition Parameter Optimization):
where R avg (K, N, M, x) is given by (6) and the optimal solution is denoted as x * (x * n,S ) n∈N ,S⊆K . The objective function of Problem 1 is convex, as it is a positive weighted sum of convex piecewise linear functions [15]. In addition, the constraints of Problem 1 are linear. Hence, Problem 1 is a convex optimization problem and can be solved using standard convex optimization techniques. Note that the number of variables in Problem 1 is 2 K · N K . Thus, the complexity of Problem 1 is huge, especially when K and N are large. In Section IV-B and Section IV-C, we shall focus on deriving equivalent simplified formulations for Problem 1 to facilitate lowcomplexity optimal solutions under an arbitrary popularity distribution and the uniform popularity distribution, respectively.
Next, we discuss the relation between the class of the centralized coded caching schemes specified by the general file partition parameter x in Algorithm 1 with the coded caching schemes in [1], [2], [6]- [8]. Based on the discussion in Section III-B, we can make the following statement. [1], [2], [6], [8]): The optimized average load for the class of the centralized coded caching schemes is no greater than those of the schemes in [1], [2], [6], [8].

Statement 1 (Relations with Schemes in
Finally, we discuss the relation between the delivery procedure in Algorithm 1 and the GCC 1 procedure in [7]. Lemma 1 (Relation with GCC 1 in [7]): For all file partition parameters, under the placement procedure in Algorithm 1, the delivery procedure in Algorithm 1 achieves the same average load as the GCC 1 procedure.
Proof: Please refer to Appendix A.
From Lemma 1, we know that the GCC 1 procedure achieves the same average load as the delivery procedure in Algorithm 1 at the optimized file partition parameter x * . The discussion on the relation with the HCD procedure is deferred to the end of Section IV-B.

B. Optimization under Arbitrary File Popularity
In this part, we first characterize structural properties of Problem 1 and simplify it without losing optimality via two steps. In step 1, we show an important structural property of Problem 1. Theorem 1 indicates that at the optimal solution to Problem 1, for all n ∈ N and s ∈ {0, 1, · · · , K}, subfiles W n,S , S ∈ {S ⊆ K : |S| = s} have the same size. By Theorem 1, without losing optimality, we can set when solving Problem 1, where s = |S| ∈ {0, 1, · · · , K}. Here, y n,s can be viewed as the ratio between the number of data units in each subfile of file W n which is of type s and the number of data units in file W n (i.e., F ). Let y (y n,s ) n∈N ,s∈{0,1,··· ,K} .
By (7), the constraints in (2), (3) and (4) of Problem 1 can be converted into the following constraints: On the other hand, by (7), the objective function of Problem 1 in (6) can be rewritten as Define D n,s {n, n+1, . . . , N} s \{n+1, n+2, . . . , N} s , which represents the set of all s-tuples with elements in {n, n + 1, ..., N} that contain at least once the element n. We further simplify (11). (11) is equivalent to Proof: Please refer to Appendix C.
Note that the above transformations will not cause any optimality loss for Problem 1. Thus, Problem 1 is equivalent to the following optimization problem.

Problem 2 (Equivalent Optimization in
Step 1): where R avg (K, N, M, y) is given by (12) and the optimal solution is denoted as y * (y * n,s ) n∈N ,s∈{0,1,··· ,K} . The objective function of Problem 2 is convex, as it is a positive weighted sum of convex piecewise linear functions [15]. In addition, the constraints of Problem 2 are linear. Hence, Problem 2 is a convex optimization problem and can be solved using standard convex optimization techniques. Note that the number of variables in Problem 2 is N (N K −1) N −1 , which is much smaller than that of Problem 1 (i.e., 2 K · N K ). However, the complexity of Problem 2 is still huge, especially when K and N are large.
In step 2, we characterize an important structural property of Problem 2.
Proof: Please refer to Appendix D.
Based on Theorem 2, we have the following result.
Based on the above analysis, Problem 2 is equivalent to the following optimization problem. where R avg (K, N, M, y) is given by (16).
The objective function of Problem 3 is linear. In addition, the constraints of Problem 3 are linear. Hence, Problem 3 is a linear optimization problem and can be solved using linear optimization techniques. Note that the number of variables in Problem 3 is (K + 1)N. The complexity for solving Problem 3 using the algorithm in [16] is O (K + 1)N .
Next, we discuss the relation between the delivery procedure in Algorithm 1 and the HCD procedure under any file partition parameter satisfying (7) and (15). Recall that in the delivery procedure in Algorithm 1, all subfiles in one coded multicast message are zero-padded to the length of the longest subfile in the coded multicast message, which may cause the "bit waste" problem and degrade the average load performance. In [14], an efficient delivery procedure for coded caching, called HCD procedure, is proposed, without specifying a placement procedure.
The HCD procedure adopts an appending method to address the "bit waste" problem. In particular, all subfiles in one coded multicast message are padded with bits from some subfiles with larger s to achieve the same length as the longest subfile in the coded multicast message.
Accordingly, these appended bits are then removed from the subfiles with larger s and do not need to be considered again when later coding these subfiles. Thus, one may expect that the HCD procedure can achieve a lower average load than the delivery procedure in Algorithm 1 under any file partition parameter. However, the following lemma shows a different result.
Lemma 4 (Relation with HCD in [14]): For all file partition parameters satisfying (7) and (15), under the placement procedure in Algorithm 1, the delivery procedure in Algorithm 1 achieves the same average load as the HCD procedure.
Proof: Please refer to Appendix G.
Recall that Theorem 1 and Theorem 2 imply that the optimized file partition parameter satisfies (7) and (15). Thus, Lemma 4 also indicates that the HCD procedure achieves the same average load as the delivery procedure in Algorithm 1 at the optimized file partition parameter. However, the HCD procedure has higher complexity than the delivery procedure in Algorithm 1 due to the involved appending method. By Lemma 1, we can also know that at the optimized file partition parameter, the HCD procedure achieves the same average load as the GCC 1 procedure.

C. Optimization under Uniform File Popularity
In this part, we consider the uniform file popularity, i.e., p 1 = p 2 = . . . = p N , and would like to characterize another structural property and further simplify Problem 3 in this case. First, we show an important structural property of Problem 3.  (8), (9) and (10) of Problem 3 can be converted into the following constraints: On the other hand, by (18), the objective function of Problem 3 in (16) can be rewritten as Based on the above analysis, under the uniform file popularity, Problem 3 is equivalent to the following problem.

Lemma 5 (Optimal Solution to Problem 4):
For cache size M ∈ 0, N K , 2N K , . . . , N , the unique optimal solution z * to Problem 4 is given by and the optimal value of Problem 4 is given by Proof: Please refer to Appendix H.
Lemma 5 indicates that, under the uniform file popularity, for any cache size M ∈ 0, N K , 2N K , . . . , N , the optimized file partition parameter z * in (23) and the optimized average load R * avg (K, N, M) in (24) for the class of the centralized coded caching schemes are the same as the file partition parameter and the worst-case load of Maddah-Ali-Niesen's centralized coded caching scheme [1].
Note that this optimality only holds for the worst-case when N ≥ K [10]. For the worst-case or the case under the uniform file popularity, the optimal load is given in [5] where a scheme which improves over the original Maddah-Ali-Niesen's centralized coded caching scheme for uncoded placement is used.

V. CONVERSE BOUND
In this section, we present an information-theoretic converse bound on the average load under an arbitrary file popularity. Denote R lb unif (K, N, M) as the converse bound on the average load under the uniform file popularity obtained in [11], where Using the genie-aided approach proposed in [7] and the converse bound R lb unif (K, N, M) derived in [11], we have the following result.
where R lb unif (·) is given by (25). The difference between Lemma 6 and Theorem 2 in [7] lies in the fact that the two results utilize two different converse bounds on the average load under the uniform file popularity.
In particular, Lemma 6 adopts the converse bound on the average load under the uniform file popularity derived in [11], while Theorem 2 in [7] utilizes a converse bound on the average load under the uniform file popularity, which is derived using a self-bounding function [7]. The purpose of replacing the converse bound for the uniform file popularity in [11] with the one in [7] is to obtain a tighter converse bound for an arbitrary file popularity. Later, in Section VI, we shall see that the presented converse bound is indeed tighter than that in [7], using numerical results.
From Lemma 6, we know that under the uniform file popularity, R lb avg (K, N, M) = R lb unif (K, N, M). This means that when the file popularity is uniform, the genie-aided converse bound in (26) reduces to the converse bound on the average load under the uniform file popularity derived in [11].

VI. NUMERICAL RESULTS
In this section, using numerical results, we first demonstrate special properties of the proposed optimal solutions. Then, we compare the proposed optimal solution with existing solutions.
Finally, we compare the presented genie-aided converse bound with existing information-theoretic converse bounds. In the simulation, as in [6], [7], [9], [14], we assume the file popularity follows Zipf distribution, i.e., p n = n −γ n∈N n −γ for all n ∈ N , where γ is the Zipf exponent.

A. Special Properties of Optimized Parameter-based Scheme
In this part, we demonstrate special properties of the centralized coded caching scheme corresponding to the optimized file partition parameter (referred to as the optimized parameterbased scheme) using numerical results. Let q * (q * n ) N n=1 , where q *  the fraction of the memory M allocated to file W n at the optimized file partition parameter. Fig. 1 illustrates y * and q * of the optimized parameter-based scheme. From Fig. 1, we can see that for all n ∈ {1, 2, . . . , N − 1} and s ∈ {1, 2, · · · , K}, y * n,s ≥ y * n+1,s , which verifies Theorem 2. Furthermore, we can see that files are classified into different groups and for any file n 1 and file n 2 within the same group, we have y * n 1 ,s = y * n 2 ,s for all s ∈ {0, 1, . . . , K} and q * n 1 = q * n 2 , which verifies Corollary 1 and validates the "grouping" idea proposed in [6]. From Fig. 1

B. Average Load Comparison
In this part, we compare the average loads of the optimized parameter-based scheme, the HCD procedure [14] at the optimized file partition parameter in Problem 3 (referred to as the HCD scheme here), the GCC 1 procedure [7] at the optimized file partition parameter in Problem 3   parameter-based scheme achieves better performance than the baseline schemes in [1], [5], [7], [8] is due to the advantage of the optimized parameter-based scheme in exploiting file popularity for efficient content placement.   Fig. 4, we see that the average load of each scheme increases with N. In addition, the optimized parameter-based scheme outperforms the other schemes in the considered regime of N. 5 Note that the HCD scheme and the GCC1 scheme cannot be implemented using a desktop when K = 10 due to huge complexity.

C. Converse Bound Comparison
In this part, we compare different information-theoretic converse bounds on the average load under an arbitrary file popularity. Fig. 5 illustrates the average load of the optimized parameterbased scheme R * avg (K, N, M), the genie-aided converse bound in (26) and the converse bounds in [7]- [9], [12]. From Fig. 5, we can see that the genie-aided converse bound in (26) is tighter than the converse bounds in [7], [8] for any cache size M. The genie-aided converse bound in (26) is tighter than the converse bounds in [9], [12] when the cache size is modest or large, and is looser than the converse bounds in [9], [12] when the cache size is small.

VII. CONCLUSION
In this work, we considered 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. We formulated the coded caching design optimization problem to minimize the average load over the considered class of schemes by optimizing the file partition parameter under an arbitrary file popularity. We showed that the optimization problem is convex, and the resulting optimal solution generally improves upon known schemes. Next, we analyzed structural properties of the optimization problem to obtain design insights and significantly reduce the complexity for obtaining an optimal solution. Under the uniform file popularity, we also obtained the closed-form optimal solution, which corresponds to Maddah-Ali-Niesen's centralized coded caching scheme. Finally, we presented an information-theoretic converse bound on average load under an arbitrary file popularity, which was shown to improve on known bounds for arbitrary file popularity for some configurations of the system parameters (in particular, for not too small cache memory). This paper opens up several directions for future research. For instance, the class of the centralized coded caching schemes can be extended to design efficient decentralized coded caching schemes to reduce the average load under an arbitrary file popularity. In addition, the average load of the optimized parameter-based scheme may be further reduced by using the improved delivery scheme of [5]. Finally, the parameter-based coded caching design approach can also be generalized to improve the performance of other coded caching schemes. Note that under the placement procedure in Algorithm 1, and µ(v 2 ) ∈ η(v 1 ). Thus, from the GCC 1 procedure, we know that assigning any two nodes v 1 and v 2 satisfying {µ(v 1 ), η(v 1 )} = {µ(v 2 ), η(v 2 )} the same color in the conflict graph corresponds to coding W µ(v 1 ),η(v 1 ) and W µ(v 2 ),η(v 2 ) together in the delivery procedure in Algorithm 1. This means that all the nodes corresponding to {µ(v), η(v)} can be assigned the same color as node v, and the corresponding subfiles W d k ,S\{k} , k ∈ S can be coded together, as in the delivery procedure in Algorithm 1. Thus, we complete the proof of Lemma 1.

APPENDIX B: PROOF OF THEOREM 1
We prove Theorem 1 by considering the following two cases.
(i) Consider s = K. In this case, there exists only one subfile of type K, i.e., W n,K , and hence Theorem 1 holds obviously.
Next, we prove the above two statements, separately.

Proof of Statement (ii)
First, we calculate the average loads under two related feasible file partition parameters.

APPENDIX E: PROOF OF COROLLARY 1
We prove Corollary 1 by proving the sufficiency and necessity. First, we prove the sufficiency.
APPENDIX F: PROOF OF LEMMA 3 By (15), for any (d 1 , . . . , d s ) ∈ D n,s , n ∈ {1, 2, · · · , N − 1} and s ∈ K, we have max k∈{1,2,··· ,s} y d k ,s−1 = y n,s−1 , s ∈ K. (45) By (12) and (45) where (a) is due to (45) (7) and (15), we know that for any k ∈ S \ S m and any k m ∈ S m , subfile W d k ,S\{k} has smaller length than subfile W d km ,S\{km} , and should be padded with bits from some subfiles W d k ,S ′ \{k} , S ⊂ S ′ ⊆ K in the HCD procedure. Consider any subset of users S ′ such that S ⊂ S ′ ⊆ K. Define S ′ m {k ∈ S ′ : d k = min l∈S ′ d l }. By the definitions of S m and S ′ m , we have (S \ S m ) ∩ S ′ m = ∅ and (S \ S m ) ∪ S ′ m ⊂ S ′ . Consider any k ∈ S \ S m and any k ′ m ∈ S ′ m . By (7), (15) and (47), we know that the size of subfile W d k ,S ′ \{k} in coded multicast message ⊕ k∈S ′ W d k ,S ′ \{k} is smaller than that of the longest subfile W d k ′ m ,S ′ \{k ′ m } in this coded multicast message. Thus, the appending method in the HCD procedure does not change the size of ⊕ k∈S ′ W d k ,S ′ \{k} . Therefore, we complete the proof of Lemma 4.