1

Uncoded Placement Optimization for Coded
Delivery
arXiv:1709.06462v2 [] 20 Mar 2018

Sian Jin, Student Member, IEEE, Ying Cui, Member, IEEE,
Hui Liu, Fellow, IEEE, Giuseppe Caire, Fellow, IEEE

Abstract
Existing coded caching schemes fail to simultaneously achieve efficient content placement for
non-uniform file popularity and efficient content delivery in the presence of common requests, and
hence may not achieve desirable average load under a non-uniform, possibly very skewed, popularity
distribution. In addition, existing coded caching schemes usually require the splitting of a file into
a large number of subfiles, i.e., high subpacketization, and hence may cause huge implementation
complexity. To address the above two challenges, we first present a class of centralized coded caching
schemes consisting of a general content placement strategy specified by a file partition parameter,
enabling efficient and flexible content placement, and a specific content delivery strategy, enabling load
reduction by exploiting common requests of different users. Then we consider two cases, namely, the
case without considering the subpacketization issue and the case considering the subpacketization issue.
In the first case, we formulate the coded caching optimization problem over the considered class of
schemes with N 2K variables to minimize the average load under an arbitrary file popularity. Imposing
some conditions on the file partition parameter, we transform the original optimization problem into
a linear optimization problem with N (K + 1) variables under an arbitrary file popularity and a linear
optimization problem with K + 1 variables under the uniform file popularity. We also show that Yu
et al.’s centralized coded caching scheme corresponds to an optimal solution of our problem and the
imposed conditions are optimal properties for the uniform file popularity. In the second case, taking into
account the subpacketization issue, we first formulate the coded caching optimization problem over the
considered class of schemes to minimize the average load under an arbitrary file popularity subject to a
subpacketization constraint involving the ℓ0 -norm. By imposing the same conditions and using an exact
DC (difference of two convex functions) reformulation method, we convert the original problem with
N 2K variables into a simplified DC problem with N (K + 1) variables. Then, we use a DC algorithm
to solve the simplified DC problem.
S. Jin, Y. Cui and H. Liu are with Shanghai Jiao Tong University, China. G. Caire is with Technical University of Berlin,
Germany.
March 21, 2018

DRAFT

2

I. I NTRODUCTION
Recently, a new class of caching schemes for content placement in user caches, referred to
as coded caching [1], have received significant interest. In [1], 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 F data units), 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. Each user can obtain the requested file based on the
received coded-multicast messages and the contents stored in its cache. The goal of [1] is to
reduce the worst-case (over all possible requests) load of the shared link in the delivery phase.
In [2], Jin et al. consider a different class of centralized coded caching schemes specified by a
general file partition parameter, and optimize the parameter to minimize the average load within
the class under an arbitrary file popularity. In [3], the parameter-based coded caching design
approach in [2] is generalized to minimize the average load in a heterogeneous setting with
nonuniform file popularity, cache size and file size. In [4], Yu et al. propose a centralized coded
caching scheme where the delivery strategy exploits the chance of load reduction in common
requests of different users. The scheme devised by Yu et al. is proved to be optimal for the
worst-case load and average load under the uniform popularity.
Note that the delivery strategies in [1]–[3] do not capture the opportunity of load reduction
in common requests of different users, and the placement strategies in [1] and [4] allocate the
same fraction of memory to each file without reflecting popularity difference. Therefore, the
coded caching strategies in [1]–[4] may not achieve desirable average load under a non-uniform,
possibly very skewed, popularity distribution. It is not known how to simultaneously achieve
efficient content placement for non-uniform file popularity and efficient content delivery in the
presence of common requests.
Another limitation of previous works is the issue of high subpacketization, i.e., the number of
non-overlapping subfiles for each file is large. In [5]–[8], the authors tackle the subpacketization
issue for decentralized coded caching. Specifically, in [5], a user grouping method is proposed
to lower the subpacketization at the expense of larger worst-case load. In [6], based on a novel
user grouping idea, the authors propose a new order-optimal decentralized random coded caching
scheme, which induces lower subpacketization than that in [5] at the same worst-case load.

3

To reduce the average load in practical regimes of finite subpacketization, the authors in [7]
and [8] propose decentralized coded caching schemes based on hierarchy greedy local graph
coloring. In [9]–[11], the authors tackle the subpacketization issue for centralized coded caching.
Specifically, in [9], Tang et al. connect coded caching to resolvable combinatorial designs and
propose a centralized coded caching scheme where the subpacketization is exponential with
respect to (w.r.t.) the number of users but significantly lower than the centralized coded caching
scheme of [1] at the cost of a marginal increase in the worst-case load. In [10], Shanmugam et al.
connect coded caching to Ruzsa-Szeméredi graphs and show the existence of a centralized coded
caching scheme where the subpacketization grows linearly with the number of users when the
number of users is very large. In [11], the authors propose a centralized coded caching scheme
with low subpacketization based on Pareto-optimal PDA (placement delivery array). Note that
the coded caching schemes in [5], [9]–[11] addressing the subpacketization issue are applicable
only for certain system parameters (e.g., the number of users, the number of files, cache size,
etc.). Furthermore, the coded caching schemes in [5], [6], [9]–[11] are not based on optimizations
and cannot guarantee desirable average loads under subpacketization constraints.
In this paper, we would like to address the above challenges in the same centralized setting
as in [1]–[4], [9]–[11], with the focus on minimizing the average load under an arbitrary file
popularity in two cases, namely, the case without considering the subpacketization issue and
the case considering the subpacketization issue. We present a class of coded caching schemes
consisting of a general content placement strategy specified by a file partition parameter, enabling
efficient and flexible content placement, and a specific content delivery strategy, enabling load
reduction by exploiting common requests of different users. Then, we focus on the average
load minimization irrespectively of the subpacketization issue. In this case, we formulate the
coded caching optimization problem over the considered class of schemes with N2K variables
to minimize the average load under an arbitrary file popularity. The average load expression is
not tractable due to the complex delivery strategy. Therefore, we impose some conditions on
the parameter to simplify the average load expression under an arbitrary file popularity and the
uniform file popularity respectively, by connecting the file request event to the “balls into bins”
problem. Based on the simplified expressions, we transform the original optimization problem
into a linear optimization problem with N(K + 1) variables under an arbitrary file popularity
and a linear optimization problem with K + 1 variables under the uniform file popularity, which

4

are much easier to solve than the original problem. We also show that Yu et al.’s centralized
coded caching scheme corresponds to an optimal solution of our problem and the imposed
conditions are optimal properties for the uniform file popularity. Next, we consider the average
load minimization subject to a constraint on subpacketization. In this case, we first formulate
the coded caching optimization problem over the considered class of schemes to minimize the
average load under an arbitrary file popularity subject to a subpacketization constraint in terms
of the ℓ0 -norm of the file partition parameter. To the best of our knowledge, this is the first work
explicitly considering a subpacketization constraint in optimization based coded caching design.
By imposing the same conditions as in the case without considering the subpacketization issue
and using the exact DC (difference of two convex functions) reformulation method in [12], we
convert the original problem with N2K variables into a simplified DC problem with N(K + 1)
variables. Then, we use a DC algorithm to solve the simplified DC problem. Numerical results
reveal that the imposed conditions do not affect the optimality of the original problem under an
arbitrary file popularity in the case without considering the subpacketization constraint. Furthermore, our results demonstrate that the optimized coded caching scheme without considering the
subpacketization constraint outperforms those in [1], [2], [4] in terms of the average load, and
the optimized coded caching scheme considering the subpacketization constraint outperforms
those in [9] and [11] in terms of both the average load and application region.
II. C ENTRALIZED C ODED C ACHING
A. Problem Setting
As in [1]–[4], [9]–[11], we consider a system with one server connected through a shared
error-free link to K ∈ N>0 users (see Fig. 1), where N>0 denotes the set of all positive integers.
The server has access to a library of N ∈ N>0 files, denoted by W1 , . . . , WN , each consisting
of F ∈ N>0 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. Each user has an isolated cache memory
of MF data units, for some real number M ∈ [0, N]. Let Zk denote the cache content for user
k. The system operates in two phases, i.e., a placement phase and a delivery phase [1]. In the
placement phase, each user is able to fill the content of its cache using the library of N files. In
the delivery phase, each user randomly and independently requests one file in N according to file
popularity distribution p , (pn )N
n=1 , where pn denotes the probability of a user requesting file

5

Fig. 1: Problem setup for coded caching.

Wn and

PN

n=1

pn = 1. Without loss of generality, we assume p1 ≥ p2 ≥ . . . ≥ pN . Let Dk ∈ N

denote the index of the file requested by user k ∈ K, and let D , (D1 , · · · , DK ) ∈ N K denote
the requests of all the K users. The server replies to these K requests by sending messages over
the shared link, which are observed by all the K users. Each user should be able to recover its
requested file from the messages received over the shared link and its cache content. Our goal
is to minimize the average load of the shared link under an arbitrary file popularity.
B. Centralized Coded Caching Scheme
In this part, we present a class of centralized coded caching schemes utilizing a general
uncoded placement strategy and a specific coded delivery strategy, which are specified by a
general file partition parameter, as summarized in Alg. 1. The general uncoded placement strategy
is the same as that in [2]. We present it here for completeness. For all n ∈ N , file Wn is
partitioned into 2K nonoverlapping subfiles Wn,S , S ⊆ K, i.e., Wn = (Wn,S : S ⊆ K). If
the number of data units in a subfile is zero, then there is no need to consider this subfile.
Thus, 2K is the maximum number of non-overlapping subfiles of a file. We say subfile Wn,S
is of type s if |S| = s [2]. User k stores Wn,S , n ∈ N , k ∈ S, S ⊆ K in its cache, i.e.,
Zk = (Wn,S : n ∈ N , k ∈ S, S ⊆ K). Let xn,S denote the ratio between the number of data
units in Wn,S and the number of data units in Wn (i.e., F ). Let xn , (xn,S )S⊆K . Let x , (xn )n∈N

6

denote the file partition parameter (vector), which will be optimized to minimize the average
load in Section III. Thus, x satisfies
0 ≤ xn,S ≤ 1,
K
X

X

∀S ⊆ K, n ∈ N ,
xn,S = 1,

(1)

∀n ∈ N ,

(2)

s=0 S∈{S⊆K:|
b
b
S|=s}

N X
K
X

X

xn,S ≤ M,

∀k ∈ K,

(3)

n=1 s=1 S∈{S⊆K:|
b
b
b
S|=s,k∈
S}

where (1) and (2) represent the file partition constraints and (3) represents the cache memory
constraint.
The coded delivery strategy is an extension of that in [4]. For all D ∈ N K , let D(D) , {Dk :
k ∈ K} denote the set of distinct files in D. For all n ∈ D(D), the server arbitrarily selects user
kn ∈ K such that Dkn = n. Let K(D) , {kn : n ∈ D(D)} denote the set of representative users
that request |D(D)| different files. Each user k ∈ S requests subfile WDk ,S\{k} , for all subset
S ⊆ K. The server broadcasts coded-multicast message ⊕k∈S WDk ,S\{k} for all subset S ⊆ K that
satisfies S ∩ K(D) 6= ∅, and all subfiles in the coded-multicast message are zero-padded to the
length of the longest subfile.1 By Lemma 1 of [4], we can conclude that each user can decode
the requested file based on the received coded-multicast messages and the contents stored in its
cache.
Remark 1: The uncoded placement in this paper is more general than that in [1], [4], [9]–
[11], and it can be optimized to minimize the average load under an arbitrary file popularity
(see Section III and Section IV). The coded delivery in this paper is more efficient than that
in [1]–[3], [5], [6], [9]–[11], since it avoids transmitting the redundant coded-multicast messages
⊕k∈S WDk ,S\{k} , S ⊆ K \ K(D) in the presence of common requests [4].
C. Average Load
Let Ravg (K, N, M, x) denote the average load for serving the K users with cache size M
under a given file partition parameter x, where the average is taken over random requests D for
1

Note that in [4], since all files are partitioned into subfiles of type t ∈ {0, 1, . . . , K}, only coded-multicast messages

⊕k∈S WDk ,S\{k} satisfying S ⊆ K, S ∩ K(D) 6= ∅ and |S| = t + 1 are transimitted.

7

Algorithm 1 Parameter-based Centralized Coded Caching
placement procedure
1: for all k ∈ K do
2:

Zk ← (Wn,S : n ∈ N , k ∈ S, S ⊆ K)

3: end for

delivery procedure
1: for s = K, K − 1, · · · , 1 do
2:
3:
4:

for S ⊆ K : |S| = s, S ∩ K(D) 6= ∅ do
server sends ⊕k∈S WDk ,S\{k}
end for

5: end for

N files, according to an arbitrary file popularity distribution p. By Alg. 1, we have
!
K
X Y
X
max xdk ,S\{k},
Ravg (K, N, M, x) =
pdk
d∈N K

k=1

b
b
=∅}
S∈{S⊆K:
S∩K(D)6

k∈S

(4)

where d , (d1 , . . . , dK ) ∈ N K and max xdk ,S\{k} is the length of the coded message ⊕k∈S Wdk ,S\{k}
k∈S

divided by F .
From (4), we can observe that the file partition parameter x fundamentally affects the average
load Ravg (K, N, M, x). In Section III, we would like to find an optimal file partition parameter
to minimize the average load in (4). The optimal file partition parameter may correspond to
high subpacketization, and hence a high file partition cost. To avoid high subpacketization, in
Section IV, we would like to find an optimal file partition parameter to minimize the average
load in (4) under a subpacketization constraint.
III. AVERAGE L OAD M INIMIZATION

WITHOUT

S UBPACKETIZATION C ONSTRAINT

In this section, we minimize the average load by optimizing the file partition parameter without
considering any subpacketization constraint.
A. Problem Formulation
We would like to minimize the average load under the file partition constraints in (1) and (2)
as well as the cache memory constraint in (3).

8

Problem 1 (Optimization for Arbitrary File Popularity):
∗
Ravg
(K, N, M) , min
x

s.t.

Ravg (K, N, M, x)
(1), (2), (3),

where Ravg (K, N, M, x) is given by (4).
The objective function of Problem 1 is convex, as it is a positive weighted sum of convex
piecewise linear functions. In addition, the constraints of Problem 1 are linear. Hence, Problem 1
is a convex optimization problem. The number of variables in Problem 1 is N2K . Thus, the
complexity of Problem 1 is huge, especially when K and N are large. In Section III-B and
Section III-C, we shall focus on deriving simplified formulations for Problem 1 to facilitate lowcomplexity optimal solutions under an arbitrary popularity distribution and the uniform popularity
distribution, respectively.
B. Optimization for Arbitrary Popularity without Subpacketization Constraint
First, we present two structural conditions on the file partition parameter x to facilitate a
low-complexity solution of Problem 1.
Condition 1 (Symmetry w.r.t. Type): For all n ∈ N and s ∈ {0, 1, · · · , K}, the values of
b = s} are the same.
xn,S , S ∈ {Sb ⊆ K : |S|
Condition 1 indicates that, for all n ∈ N and s ∈ {0, 1, · · · , K}, subfiles Wn,S , S ∈ {Sb ⊆

b = s} have the same size. Recall that all subfiles in one coded-multicast message
K : |S|

are zero-padded to the length of the longest subfile in the coded-multicast message, causing
the “bit waste” effect [2]. Thus, imposing Condition 1 can reduce the variance of the lengths of
messages involved in the coded-multicast XOR operations, hence addressing “bit waste” problem
and increasing coded-multicasting opportunities. By Condition 1, we can set
xn,S = yn,s,

∀S ⊆ K, n ∈ N ,

(5)

where s = |S| ∈ {0, 1, · · · , K}. Here, yn,s can be viewed as the ratio between the number of
data units in each subfile of type s of file Wn and the number of data units in file Wn (i.e., F ).
Let yn , (yn,s)s∈{0,1,··· ,K} and y , (yn )n∈N .

9

Condition 2 (Monotonicity w.r.t. Popularity): For all n ∈ {1, 2, . . . , N−1} and s ∈ {1, 2, · · · , K},
when pn ≥ pn+1 ,
yn,s ≥ yn+1,s .

(6)

Condition 2 indicates that, for all n ∈ {1, 2, . . . , N − 1} and s ∈ {1, 2, · · · , K}, when pn ≥
b = s} is no smaller than that of subfiles
pn+1 , the size of subfiles Wn,S , S ⊆ {Sb ⊆ K : |S|
b = s}. Intuitively, imposing Condition 2 can reduce the average
Wn+1,S , S ⊆ {Sb ⊆ K : |S|

load, by dedicating more memory to a more popular file. Since the expression of the objective
function in (4) is complex, unlike in [2], it is difficult to prove that Conditions 1 and 2 hold for
the optimal file partition parameter under any arbitrary file popularity. Later, in Section V, the
numerical results will verify that the two conditions are optimal properties. That is, imposing
the two conditions will not lose optimality of Problem 1.
Next, we simplify Problem 1 under Conditions 1 and 2. First, we introduce some notae u,h1i ≤ D
e u,h2i ≤ . . . ≤
tions. Consider the number of representative users |K(D)| = u. Let D

e u,hK−ui denote (Dk )
e
D
k∈K\K(D) arranged in ascending order, so that Du,hii is the i-th smallest.
h
i
′
e u,hii = n
e u,hii = n , ∀i = 1, . . . , K − u. Note that the file request event D
Let Pi,u,n
, Pr D
can be treated as the “balls into bins” problem, i.e., K balls are placed i.i.d. into N bins

and each into bin n with probability pn . Let Kn denote the number of users requesting file
PN
PN
Pn−1
n. Note that
n=1 Kn = K and
n=1 1[Kn > 0] = u. Let An ,
n′ =1 1[Kn′ > 0],
PN
Pn−1
Bn,1 , n′ =1 Kn′ and Bn,2 , n′ =n+1 Kn′ . Let LAn ,1 , {L ⊆ {1, 2, . . . , n − 1} : |L| = An }.

Let LAn ,2 , {L ⊆ {n + 1, n + 2, . . . , N} : |L| = u − An − 1}. Let
)
(
X
|L|
αn′ = Bn,1 ,
ABn,1 ,L , (αn′ )n′ ∈L ∈ N>0 :
n′ ∈L

where L ∈ LAn ,1 . Let

ABn,2 ,L ,

(

(αn′ )n′ ∈L ∈

|L|
N>0

:

X

n′ ∈L

αn′ = Bn,2

)

,

where L ∈ LAn ,2 . Let N denote the set of all natural numbers. Define
K!
,
m1 !m2 !(K−m1 −m2 )!

K
m1 ,m2 ,K−m1 −m2



,

where m1 ∈ N, m2 ∈ N and m1 + m2 ≤ K. By using results for the “balls

into bins” problem and considering Conditions 1 and 2, we have the following result.
Lemma 1 (Simplification of Problem 1 for Arbitrary File Popularity): Under Conditions 1 and 2,
Problem 1 can be converted into:

10

Problem 2 (Simplified Problem of Problem 1 for Arbitrary File Popularity):
e∗ (K, N, M, y) , min
R
avg
y

s.t.

eavg (K, N, M, y)
R

yn,s ≥ yn+1,s ,

0 ≤ yn,s ≤ 1, ∀s ∈ {0, 1, · · · , K}, n ∈ N ,
K  
X
K
yn,s = 1, ∀n ∈ N ,
s
s=0

K 
N X
X
K−1
yn,s ≤ M,
s
−
1
n=1 s=1

where
eavg (K, N, M, y) ,
R
−

N
K  X
X
K
s=1

s

′
Pi,u,n

n=1

X

is given in (12)-(15).

N
X

pn ′

n′ =n

!s

−

N
X

n′ =n+1

pn ′

!s !

(7)
(8)
(9)

(10)

yn,s−1

N
X K − u − i X
X K − u K−u
′
Pi,u,n
yn,s−1,
s
−
1
s
n=1
s=1
i=1

min{K,N } K−u 
u=1

and

∀n ∈ {1, 2, . . . , N − 1}, s ∈ {1, 2, · · · , K}

(11)

Proof: Please refer to Appendix A.
Problem 2 is a linear optimization problem with N(K + 1) variables and can be solved by
using linear optimization techniques.
C. Optimization for Uniform Popularity without Subpacketization Constraint
In this part, we consider a special case, i.e., the uniform file popularity (pn =

1
,
N

for all

n ∈ N ). First, we present another structural condition on the file partition parameter.
Condition 3 (Symmetry w.r.t. File): For all n ∈ {1, 2, . . . , N − 1} and s ∈ {1, 2, · · · , K},
when pn = pn+1 ,
yn,s = yn+1,s .

(16)

Condition 3 indicates that for all n ∈ {1, 2, . . . , N − 1} and s ∈ {1, 2, · · · , K}, when pn =
b = s} is the same as that of subfiles
pn+1 , the size of subfiles Wn,S , S ⊆ {Sb ⊆ K : |S|
b = s}. Condition 3 ensures zero variance of the lengths of messages
Wn+1,S , S ⊆ {Sb ⊆ K : |S|

involved in the coded-multicast XOR operations, hence avoiding “bit waste” effect and increasing
coded-multicasting opportunities. Later, we shall show that imposing this condition will not lose
optimality of Problem 2.

11

′
Pi,u,n

X

=

X

X

a∈{1,...,u−2} b1 ∈{a,...,i+a−1} b2 ∈{u−a−1,...,K−i−a−1}

X

×

X

L1 ∈La,1 (αn′ )n′ ∈L ∈Ab1 ,L1
1

X

+

b2 ∈{u−1,...,K−2}

X

+

b1 ∈{u−1,...,K−2}

′
Pi,u,n

X

=

b1 !

Q

n′ ∈L

 
K
P K−b2
b2 n

 
K
P K−b1
b1 n

αn′ !
1

Y


K
P K−b1 −b2
b1 , K − b1 − b2 , b2 n

X

α

Pn′n′

n′ ∈L1

X



L2 ∈La,2 (αn′ )n′ ∈L ∈Ab2 ,L2
2

X

Q

X

L1 ∈Lu−1,1 (αn′ )n′ ∈L ∈Ab1 ,L1
1

X

X

b2 !

n′ ∈L2 αn′ !

L2 ∈L0,2 (αn′ )n′ ∈L ∈Ab2 ,L2
2

X

X

X

X

L1 ∈La,1 (αn′ )n′ ∈L ∈Ab1 ,L1
1

X

+

b1 ∈{u−1,...,K−2}

′
Pi,u,n

=

X

Q

n′ ∈L

 
K
P K−b1
b1 n

Y

b1 !

n′ ∈L1 αn′ !

αn′ !
1

n′ ∈L1

X



L1 ∈Lu−1,1 (αn′ )n′ ∈L ∈Ab1 ,L1
1

X

X

a∈{1,...,n−1} b1 ∈{a,...,i+a−1} b2 ∈{u−a−1,...,K−i−a−1}

×

X

X

L1 ∈La,1 (αn′ )n′ ∈L ∈Ab1 ,L1
1

+

X

b2 ∈{u−1,...,K−2}

′
Pi,u,n
=

Q

b1 !
n′ ∈L

 
K
P K−b2
b2 n

X

αn′ !
1

X

Y

α

Pn′n′

n′ ∈L1

b1 !

n′ ∈L

αn′ !
1

X

X

L1 ∈La,1 (αn′ )n′ ∈L ∈Ab1 ,L1
1

×

X

X

L2 ∈La,2 (αn′ )n′ ∈L ∈Ab2 ,L2
2

Q

b1 !

n′ ∈L1

Q

αn′ !

b2 !

n′ ∈L2 αn′ !

α

Pn′n′ , u ≤ n, u + n ≤ N + 1

n′ ∈L1

Y

Q

Y

n′ ∈L

Y

b2 !

n′ ∈L

αn′ !
2

Y

α

Pn′n′

n′ ∈L2

α

Pn′n′ , u ≤ n, u + n > N + 1

n′ ∈L1

(13)


K
P K−b1 −b2
b1 , K − b1 − b2 , b2 n

X

X

X

Q

b2 !

n′ ∈L

αn′ !
2

a∈{u−1+n−N,...,n−1} b1 ∈{a,...,i+a−1} b2 ∈{u−a−1,...,K−i−a−1}

×

Y



L2 ∈L0,2 (αn′ )n′ ∈L ∈Ab2 ,L2
2

X

α

L2 ∈La,2 (αn′ )n′ ∈L ∈Ab2 ,L2
2

X

n′ ∈L2


K
P K−b1 −b2
b1 , K − b1 − b2 , b2 n
X

Q

α

Pn′n′

Pn′n′

L2 ∈La,2 (αn′ )n′ ∈L ∈Ab2 ,L2
2

X

αn′ !
2

(12)

X

α

Pn′n′

n′ ∈L

n′ ∈L2

b1 !

Q

a∈{u−1+n−N,...,u−2} b1 ∈{a,...,i+a−1} b2 ∈{u−a−1,...,K−i−a−1}

×

Y

Y

b2 !

Q

Y

Q

b2 !
n′ ∈L

αn′ !
2

Y

α

Pn′n′

n′ ∈L2

α

Pn′n′ , u > n, u + n ≤ N + 1

n′ ∈L2

(14)



K
P K−b1 −b2
b1 , K − b1 − b2 , b2 n

α

Pn′n′
1

α

Pn′n′ , u > n, u + n > N + 1

(15)

n′ ∈L2

By Condition 3, we can set
yn,s = zs ,

∀s ∈ {0, 1, · · · , K}, n ∈ N .

(17)

12

Here, zs can be viewed as the ratio between the number of data units in each subfile of type s
of any file and the number of data units in any file (i.e., F ). Let z , (zs )s∈{0,1,··· ,K}.
Next, we simplify Problem 1 under Conditions 1 and Condition 3. First, we introduce some
notations. Let Pu′′ , Pr [|K(D)| = u], where u ∈ {1, 2, . . . , min{K, N}}. Note that event
|K(D)| = u corresponds to the event in the “balls into bins” problem that there are u nonempty
bins after placing K balls uniformly at random into N bins. By using results for the “balls
into bins” problem in the uniform case [13] and considering Conditions 1 and 3, we have the
following result.
Lemma 2 (Simplification of Problem 1 for Uniform File Popularity): Under Conditions 1 and 3,
Problem 1 can be converted into:
Problem 3 (Simplified Problem of Problem 1 for Uniform File Popularity):
min{K,N }
K−u−1
K−1
X K − u
X
X K 
′′
∗
b
zs
Pu
zs −
Ravg (K, N, M) , min
z
s+1
s+1
s=0
u=1
s=0
s.t.

where

0 ≤ zs ≤ 1, s ∈ {0, 1, · · · , K},
K  
X
K
zs = 1,
s
s=0
K  
X
KM
K
szs ≤
.
s
N
s=0
 
K 

(18)
(19)

(20)


u!
Pu′′ =
,
K
u N
N
u

(21)

 
K 
and
is the Stirling number of the second kind.
u
Proof: Please refer to Appendix B.

Problem 3 is a linear optimization problem with K + 1 variables and can be solved more

efficiently than Problem 1.
Finally, we discuss the relation between an optimal solution of Problem 3 and Yu et al.’s
centralized coded caching scheme [4].2 Let z∗ , (zs∗ )s∈{0,1,··· ,K} denote an optimal solution of
2

Yu et al.’s centralized coded caching scheme focuses on cache size M ∈ {0,

N 2N
,
K K

, . . . , N }, so that

{0, 1, . . . , K}. For general M ∈ [0, N ], the worst-case load can be achieved by memory sharing.

KM
N

is an integer in

13

Problem 3. Using KKT conditions, we have

 N 2N
Lemma 3 (Optimal Solution to Problem 3): For cache size M ∈ 0, K
, K , . . . , N , z∗ is an

optimal solution to Problem 3, where


 K1 ,
( KM
)
∗
N
zs =

0,

s=

KM
N

(22)

s ∈ {0, 1, · · · , K} \

{ KM
},
N

and the optimal value of Problem 3 is given by3
K(1 − M/N)
=
−
1 + KM/N
Proof: Please refer to Appendix C.
b∗ (K, N, M)
R
avg

min{K,N }

X
u=1

Pu′′



 

K−u . K
KM .
KM
+1
N
N

(23)

Lemma 3 indicates that Yu et al.’s centralized coded caching scheme corresponds to an optimal
b∗ (K, N, M) in (23) is equivalent
solution of Problem 3. In addition, the optimal average load R
avg

to than that in [4]. Specifically, the first term in (23) corresponds to the worst-case load in [1] and

the second term in (23) indicates the load reduction and is more tractable than that in [4]. Note
that it has been shown that Yu et al.’s centralized coded caching scheme is optimal among all
uncoded placement and all delivery under the uniform file popularity [4]. Thus, for the uniform
file popularity, Conditions 1, 2 and 3 are actually optimal properties.
IV. AVERAGE L OAD M INIMIZATION

WITH

S UBPACKETIZATION C ONSTRAINT

In this section, we minimize the average load by optimizing the file partition parameter under
a subpacketization constraint which is given by

where kxk0 ,

P

P

kxk0 ≤ Fb,

(24)

1 [xn,S 6= 0] ∈ {0, 1, . . . , N2K } denotes the ℓ0 -norm of the vector
x, i.e., the total number of subfiles for N files, and Fb ∈ {N, N + 1, . . . , N2K } represents the
n∈N

S∈K

subpacketization limit. To the best of our knowledge, this is the first work explicitly considering
a subpacketization constraint in optimization based coded caching design.
3

In this paper, we define

n
k



= 0 when k > n [4].

14

A. Problem Formulation
In this part, we minimize the average load under the file partition constraints in (1) and (2),
the cache memory constraint in (3), and the subpacketization constraint in (24).
Problem 4 (Optimization for Arbitrary File Popularity with Subpacketization Constraint):
†
Ravg
(K, N, M) , min
x

s.t.

Ravg (K, N, M, x)
(1), (2), (3), (24),

where Ravg (K, N, M, x) is given by (4).
Compared with Problem 1, Problem 4 has an extra constraint, i.e., the subpacketization
constraint in (24). There are two main challenges in solving Problem 4. First, Problem 4 is
an NP-Hard problem due to the discontinuous constraint in (24) involving the ℓ0 -norm [12].
Second, the number of variables in Problem 4 is N2K , which is huge, especially when K and
N are large.
B. Simplified Formulation
There are extensive research dealing with optimization problems involving the ℓ0 -norm. Those
works can be divided into three main categories according to the way of treating the ℓ0 -norm, i.e.,
convex approximation, non-convex approximation, and non-convex exact reformulation [14]. For
the category of convex approximation, one of the best known approaches is approximating the
ℓ0 -norm with the ℓ1 -norm (denoted as kxk1 ) [14]. If the original optimization problem is convex
except the discontinuous constraint involving the ℓ0 -norm, this convex approximation approach
can transform the original NP-Hard problem involving the ℓ0 -norm into a convex problem.
However, it has been shown that an optimal solution of the approximated convex problem is not
always sparse (may not be a feasible solution of the original problem) [15]. For the category of
non-convex approximation, a variety of sparsity-inducing penalty functions, e.g., the ℓp pseudonorm with 0 < p < 1 [16], exponential concave function [17], and logarithmic function [18], have
been proposed to approximate the ℓ0 -norm. In general, non-convex approximation can provide
better sparsity than convex approximation, but may not provide an optimal solution of the original
problem. Few works focus on non-convex exact reformulation, which is proposed to guarantee the
equivalence between the reformulated problem and the original problem. Using exact penalty

15

techniques, [14] and [19] show that the reformulated problems with suitable parameters are
equivalent to the original problems. However, the reformulated problems are quite convoluted
as they rely on too many parameters [12]. In recent work [12], the authors propose an exact
DC (difference of two convex functions) reformulation which is simpler than the reformulated
problems proposed in [14] and [19] and then use a DC algorithm to solve the DC problem. In
the following, to obtain a simple equivalent problem of the original one, we use the exact DC
reformulation method in [12].4
We first simplify Problem 4 to facilitate a low-complexity solution. Using the method for
obtaining Problem 2 and Theorem 1 of [12] for simplifying the constraint in (24) under Conditions 1 and 2, we have the following result.
Lemma 4 (Simplification for Problem 4 for Arbitrary File Popularity): Under Conditions 1 and 2,
Problem 4 can be converted into:
Problem 5 (Simplified Problem of Problem 4 for Arbitrary File Popularity):
e† (K, N, M, y) , min
R
avg
y

s.t.

eavg (K, N, M, y)
R

(7), (8), (9), (10),

kW yklgst,Fb = N,
eavg (K, N, M, y) is given by (11),
where R

J

 J



·

W ,

·



·


(25)



J














(26)

denotes the block matrix of the dimension N2K × (K + 1)N, with N blocks of matrix J ,
(jm,n )m∈{1,...,2K },n∈{1,...,K+1} as its diagonal blocks and zero matrices as its non-diagonal blocks,

P K
Given the constraint in (9), the ℓ1 -norm of x is equal to a constant, i.e., kxk1 = N2
i=1 xi = N . Thus, replacing kxk0 with
kxk1 in (24) results in the constraint N ≤ Fb , which always holds and cannot restrain x.
4

16

and the element of row m and column n of J is



1, Pn−1 K < m ≤ Pn
i=1 i−1
i=1
jm,n =

0, otherwise
Proof: Please refer to Appendix D.

K
i−1



.

(27)

The number of variables in Problem 5 is NK, which is much smaller than that of Problem 4,

i.e., N2K . In addition, compared with Problem 2, Problem 5 has an extra constraint in (25),
which is non-convex but has two advantages over the subpacketization constraint in (24): (i)
kW yklgst,Fb in (25) is a convex function which will enable the transformation of the original
problem into a DC programming problem, which can be solved by a DC algorithm in polynomial
time; (ii) a subgradient of kW yklgst,Fb can be efficiently computed, making the DC algorithm an
efficient one. In Section IV-C, we will see the above two advantages clearly.
C. Penalized Formulation and DC Algorithm
To facilitate the solution, we transform Problem 5 into a DC problem by using the exact DC
reformulation method in [12].
Problem 6 (Penalized Formulation):
min
y

s.t.

eavg (K, N, M, y) − ρkW yk b
R
lgst,F
(7), (8), (9), (10),

eavg (K, N, M, y) is given by (11) and the penalty parameter ρ > 0.
where R

The objective function of Problem 6 is a difference of two convex functions. In addition,

the constraints of Problem 6 are linear. Thus, Problem 6 is a DC problem and an efficient DC
algorithm can be used to obtain a stationary point of Problem 6.
Let Υ , {y : (7), (8), (9), (10)} and V(Υ) be the vertex set of Υ. By Theorem 1 in [20], we
show the equivalence between Problem 5 and Problem 6.
Lemma 5 (Exact Penalty): For all ρ > ρ0 ,

e†avg (K,N,M )−R
e∗avg (K,N,M )
R

min{N −kW yklgst,Fb :(7),(8),(9),(10),N >kW yklgst,Fb }

, where

e∗ (K, N, M) and R
e† (K, N, M) are the optimal values of Problem 2 and Problem 5, respecR
avg
avg

tively, Problem 5 and Problem 6 have the same optimal solution.
Proof: Please refer to Appendix E.

Lemma 5 shows that Problem 5 is equivalent to Problem 6 if the penalty parameter ρ is
sufficiently large. Thus, in the following, we solve Problem 6 instead of Problem 5 by using a

17

DC algorithm. The main idea of the DC algorithm is to iteratively solve a sequence of convex
problems, each of which is obtained by linearizing the second term of the objective function
of the DC problem. A subgradient of the second term of the objective function is required in
the linearization in each iteration. Thus, to solve Problem 6, we first obtain a subgradient of
kW yklgst,Fb by extending the closed-form expression of a subgradient of kyklgst,Fb given in [12].
Lemma 6 (Subgradient of kW yklgst,Fb ): g(y) , (gi )i∈{1,2,...,KN } is a subgradient of kW yklgst,Fb ,
where

g[i] =








([i]−1)

Fb −




0,



K
mod (K+1)

PI−1
i=1

([i]−1)

i ∈ {1, . . . , I − 1}

,
K
mod (K+1)


,

i=I

otherwise
P
[i] represents the index of i-th largest element in y, and I satisfies I−1
i=1

PI
K
b
and i=1 ([i]−1) mod (K+1) > F .

,

(28)



K
([i]−1) mod (K+1)

≤ Fb

Proof: Please refer to Appendix F.

Then, based on the subgradient g(y) given in Lemma 6, we can obtain a stationary point
of Problem 6 using the DC algorithm as summarized in Algorithm 2. Note that the obtained
solution may not be a feasible solution of Problem 5. As in [14], to approach the globally
optimal solution of Problem 5, we obtain multiple stationary points of Problem 6 by performing
the DC algorithm multiple times, each with a random initial feasible point of Problem 6, and
adopt the stationary point with the lowest average load among all the obtained stationary points
of Problem 6 that are also feasible solutions of Problem 5.
Algorithm 2 DC Algorithm for Solving Problem 6
1: Find an initial feasible point y(0) of Problem 6 and set t = 0
2: repeat
3: Set y(t+1) to be an optimal solution of the convex problem:

min
y

T

eavg (K, N, M, y) − ρg y(t) y
R

s.t. (7), (8), (9), (10)
4: Set t = t + 1
5: until


 

eavg (K, N, M, y(t−1) ) − ρkW y(t−1) k
eavg (K, N, M, y(t) ) − ρkW y(t) k
−
R
R
b
b
lgst,F
lgst,F ≤ δ

18

V. N UMERICAL R ESULTS
In the simulation, we assume the file popularity follows Zipf distribution, i.e., pn =

−γ
P n
−γ
n∈N n

for all n ∈ N , where γ is the Zipf exponent. Fig. 2 (a) shows the optimal values of Problems 1,
2 and 3, verifying that Conditions 1, 2 and 3 are optimal conditions when the subpacktization
constraint is not considered. Fig. 2 (b) compares the average load of our optimized parameterbased scheme, the average loads of the centralized coded caching schemes in [1], [2], [4], the
genie-aided converse bound in [2] and the conserve bound in [21], all without considering the
subpacketization issue. From Fig. 2 (b), we can see that the optimized parameter-based scheme
outperforms the three baseline schemes. The gain over Jin et al.’s optimized centralized coded
caching scheme follows by using an extended version of the improved delivery strategy of Yu
et al., that takes advantage of common requests (which occur with positive probability in the
case of random demands). The gain over Yu et al.’s centralized coded caching scheme is due to
exploiting the explicit knowledge of the file popularity in the optimization of content placement.5
In addition, the optimized average load is close to the converse bounds, implying that the optimal
value obtained by solving Problem 2 is close to optimal.
Fig. 3 (a) and Fig. 3 (b) compare the average load of our optimized parameter-based scheme
considering the subpacketization constraint, the average loads of Tang et al.’s scheme [9] and
Pareto-optimal PDA [11] both considering the subpacketization issue as well as the average load
of our optimized parameter-based scheme without considering the subpacketization constraint
(serving as a lower bound of the proposed one considering the subpacketization constraint). Note
that in Fig. 3 (a), for the considered K, N, M, Tang et al.’s scheme is applicable only at Fb = 20

and Pareto-optimal PDA is applicable only at Fb = 20 and Fb = 100; in Fig. 3 (b), for the
considered K, N, M, Tang et al.’s scheme and Pareto-optimal PDA are not applicable at any Fb.

From Fig. 3 (a) and Fig. 3 (b), we can see that our optimized parameter-based scheme outperforms
Tang et al.’s scheme and Pareto-optimal PDA in terms of both the average load and application
region. In addition, from Fig. 3 (b), we can see that our optimized parameter-based scheme
considering the subpacketization constraint can achieve significantly lower subpacketization than
the one without considering the subpacketization constraint, at the cost of a small increase of
5

It has been proved in [2] that the optimized parameter-based scheme in [2] outperforms Maddah-Ali–Niesen’s centralized

coded caching scheme [1].

19
2.5

Optimal
Optimal
Optimal
Optimal

2

value
value
value
value

of
of
of
of

Problem
Problem
Problem
Problem

3,
1,
2,
1,

γ
γ
γ
γ

4

=0
=0
= 1.5
= 1.5

Optimized parameter-based without subpack. constr.
Jin et al.’s centralized
Yu et al.’s centralized
Maddah-Ali–Niesen’s centralized
Genie-aided bound [2]
Converse bound [21]

Average Load

Average Load

3
1.5

1

2

1
0.5

0

0
0

1

2

3

4

0

2.5

5

7.5

10

Cache Size M

Cache Size M

(a) K = 3, N = 4.

(b) K = 4, N = 10, γ = 1.5.

Fig. 2: Average load versus M under Zipf distribution. Note that Maddah-Ali–Niesen’s and Yu et al.’s centralized
coded caching schemes mainly focus on the cache size M ∈



N 2N
0, K
, K , . . . , N . For other M ∈ [0, N ], the

average loads of Maddah-Ali–Niesen’s and Yu et al.’s centralized coded caching schemes are achieved by memory
sharing [1], [4].

the average load. This means that sacrificing a small average load gain can achieve a huge
subpacketization reduction under the considered setting.
VI. C ONCLUSION
In this paper, we first presented a class of centralized coded caching schemes consisting of
a general content placement strategy specified by a file partition parameter, enabling efficient
and flexible content placement, and a specific content delivery strategy, enabling load reduction
by exploiting common requests of different users. Then we considered two cases: the case
without considering the subpacketization issue and the case considering the subpacketization
issue. In the first case, we formulated the coded caching optimization problem over the considered
class of schemes with N2K variables to minimize the average load under an arbitrary file
popularity. Imposing some conditions on the file partition parameter, we transformed the original
optimization problem into a linear optimization problem with N(K + 1) variables under an
arbitrary file popularity and a linear optimization problem with K + 1 variables under the
uniform file popularity. In the second case, we first formulated the coded caching optimization
problem over the considered class of schemes to minimize the average load under an arbitrary

20
1.05

2.4

Optimized parameter-based under subpack. constr.
Lower bound
Tang et al.’s centralized
Pareto-optimal PDA

1

2.2
2

Average Load

Average Load

0.95
0.9
0.85

1.8
1.6

0.8

1.4

0.75

1.2

0.7
10

Optimized parameter-based under subpack. constr.
Lower bound

30

50

70

90

1
10

110

70

Subpacketization Limit Fb

130

190

250

310

370

Subpacketization Limit Fb

(a) K = 6, N = 5, M = 2.5, γ = 1.3.

(b) K = 6, N = 10, M = 4, γ = 0.5.

Fig. 3: Average load versus Fb under Zipf distribution. To obtain the average load of our optimized parameter-based

scheme under the subpacketization constraint, we solve Problem 6 with ρ = 500 by performing Algorithm 2 with

δ = 0.001 100 times each with a random initial feasible point and adopt the locally optimal solution with the
lowest average load among all the obtained locally optimal solutions of Problem 6 that are also feasible solutions
of Problem 5.

file popularity subject to a subpacketization constraint involving the ℓ0 -norm. Next, imposing
the same conditions and using the exact DC reformulation method, we converted the original
problem with N2K variables into a simplified DC problem with N(K + 1) variables. Then, we
used a DC algorithm to solve the simplified DC problem.
A PPENDIX A: P ROOF

OF

L EMMA 1

By (5), it can be easily shown that the constraints in (1), (2) and (3) of Problem 1 can be
converted into (8), (9) and (10). Now, we show that the objective function of Problem 1 in (4)
can be converted into the objective function of Problem 2 in (11). First, by (5), we have
! K
K
X
X
Y
(a) X
Ravg (K, N, M, x) =
max ydk ,s−1
pdk
−

d∈N K

k=1

X

K
Y

d∈N K

k=1

pdk

!

s=1 S∈{S⊆K:|
b
b
S|=s}

K
X

X

k∈S

s=1 S∈{S⊆K\K(d):|
b
b
S|=s}

max ydk ,s−1
k∈S

21
K   N
(b) X K X

=

s

s=1

−

X

d∈N K

n=1

K
Y

pdk

k=1

!

N
X

n′ =n

pn ′

!s

K
X

−

X

N
X

pn ′

n′ =n+1

!s !

yn,s−1

max ydk ,s−1 ,

s=1 S∈{S⊆K\K(d):|
b
b
S|=s}

(29)

k∈S

where (a) is due to (5), and (b) is due to Lemma 3 in [2]. Then, we further simplify the second
term in (29):
X

K
Y

X

K
Y

d∈N K

pdk

k=1

!

K
X

X

s=1 S∈{S⊆K\K(d):|
b
b
S|=s}

max ydk ,s−1
k∈S

! K−|K(d)| K−|K(d)| 

X
X
K − |K(d)| − i
ydki ,s−1
pdk
=
s−1
s=1
i=1
k=1
d∈N K
! K−u K−u−s+1 

min{K,N }
K
X X
X X Y
K −u−i
pdk
ydki ,s−1
=
s−1
s=1
u=1
i=1
k=1
d∈Du
!

min{K,N } K−u K−u−s+1 
K
X X X
K −u−i X Y
pdk ydki ,s−1
=
s
−
1
u=1
s=1
i=1
k=1
d∈D

(c)

u

=

min{K,N } K−u K−u−s+1 

X
u=1

X
s=1

X
i=1

 N
K −u−i X ′
Pi,u,n yn,s−1,
s−1
n=1

where dki denotes the i-th most popular file in (Dk )k∈K\K(d) , (c) is derived by using the same simo
n
P
1[d
>
0]
=
u
.
plification method in the proof of Proposition 1 in [3], and Du , d ∈ N K : N
n
n=1
e u,hii = n to the “balls into bins” problem.
It remains to derive P ′ by connecting the event D
i,u,n

Note that the event that K balls are placed in an i.i.d. manner into N bins where each of the K

balls is placed into bin n′ (the bin with index n′ ) with probability pn′ corresponds to the event that
each user randomly and independently requests file n′ ∈ N with probability pn′ (represented

by random variable Dk , k ∈ K). Let Eu denote the event that there are exactly u nonempty
bins, which corresponds to the event that there are u representative users, i.e., |K(D)| = u. Let
1,{1,2,...,n−1}

Eb1 ,a,u

denote the event that b1 balls fall into a different bins with indices smaller than

or equal to n − 1, which corresponds to the event that there are b1 users requesting a different
2,{n+1,n+2,...,N }

files with file indices smaller than or equal to n − 1. Let Eb2 ,u−a−1,u

denote the event that

b2 balls fall into u − a − 1 different bins with indices larger than or equal to n + 1, which
corresponds to the event that there are b2 users requesting u − a − 1 different files with file
3,{n}

indices larger than or equal to n + 1. Let Eb3 ,1,u denote the event that b3 balls fall into bin n,

22

which corresponds to the event that there are b3 users requesting file n. Let Θa (u, n) denote the
1,{1,2,...,n−1}

range of a in Eb1 ,a,u

2,{n+1,n+2,...,N }

1,{1,2,...,n−1}

in Eb1 ,a,u

and

2,{n+1,n+2,...,N }

and Eb2 ,u−a−1,u

and let Θb (n, u, a) denote the range of (b1 , b2 , b3 )

3,{n}

, Eb2 ,u−a−1,u
and Eb3 ,1,u for a given a, where



{0, 1, . . . , u − 1},
u ≤ n, u + n ≤ N + 1






{u − 1 + n − N, . . . , u − 1}, u ≤ n, u + n > N + 1
Θa (u, n) =
,


{0,
.
.
.
,
n
−
1},
u
>
n,
u
+
n
≤
N
+
1






{u − 1 + n − N, . . . , n − 1}, u > n, u + n > N + 1

(30)




{(b1 , b2 , b3 ) : b1 ∈ {a, . . . , K}, b2 ∈ {u − a − 1, . . . , K}, b1 + b2 + b3 = K}, a ∈ {1, . . . , u − 2} ∩ Θa (u, n)



Θb (n, u, a) = {(b1 , b2 , b3 ) : b1 = 0, b2 ∈ {u − 1, . . . , K}, b1 + b2 + b3 = K},
a ∈ {0} ∩ Θa (u, n)




{(b , b , b ) : b ∈ {u − 1, . . . , K}, b = 0, b + b + b = K},
a ∈ {u − 1} ∩ Θa (u, n).
1 2 3
1
2
1
2
3
(31)

We know that
[

Eu =



[

a∈Θa (u,n) (b1 ,b2 ,b3 )∈Θb (a)

1,{1,2,...,n−1}

Eb1 ,a,u

2,{n+1,n+2,...,N }

∩ Eb2 ,u−a−1,u


3,{n}
∩ Eb3 ,1,u .

(32)

Then, remove one ball from each of the |K(D)| nonempty bins and consider the remaining
1,{1,2,...,n−1}

balls, which corresponds to consider the requests in (Dk )k∈K\K(D) . Let ξi−1

denote the

event that there are at most i − 1 balls placed in the bins with indices smaller than or equal to
2,{1,2,...,n}

n − 1 and let ξi

denote the event that there are at least i balls placed in the bins with
1,{1,2,...,n−1}

2,{1,2,...,n}

indices smaller than or equal to n. Note that ξi−1
∩ ξi
∩ Eu is equivalent to the
h
i
h
i
e u,hii = n, implying that P ′ = Pr D
e u,hii = n = Pr ξ 1,{1,2,...,n−1} ∩ ξ 2,{1,2,...,n} ∩ Eu .
event D
i,u,n
i−1
i
1,{1,2,...,n−1}

Similar to (32), ξi−1

1,{1,2,...,n−1}

=

ξi−1
[

2,{1,2,...,n}

∩ ξi

2,{1,2,...,n}

∩ ξi
[

∩ Eu can be represented as

∩ Eu


1,{1,2,...,n−1}
2,{n+1,n+2,...,N }
3,{n}
Eb1 ,a,u
∩ Eb2 ,u−a−1,u
∩ Eb3 ,1,u ,

(33)

e b (i,u,n,a)
a∈Θa (u,n) (b1 ,b2 ,b3 )∈Θ

e b (i, u, n, a) denotes the range of (b1 , b2 , b3 ). In the following, we determine Θ
e b (i, u, n, a):
where Θ
•

1,{1,2,...,n−1}

For any a ∈ {1, . . . , u − 2} ∩ Θa (u, n), by Eb1 ,a,u

b1 ≤ i + a − 1;

1,{1,2,...,n−1}

and ξi−1

, we have

(34)

23

2,{n+1,n+2,...,N }

by Eb2 ,u−a−1,u

2,{1,2,...,n}

and ξi

, we have
b2 ≤ K − i − a − 1.

(35)

By (34), (35) and (31), we have
e b (i, u, n, a)
Θ

= {(b1 , b2 , b3 ) : b1 ∈ {a, . . . , i + a − 1}, b2 ∈ {u − a − 1, . . . , K − i − a − 1}, b1 + b2 + b3 = K}
(36)
for all a ∈ {1, . . . , u − 2} ∩ Θa (u, n).
•

1,{1,2,...,n−1}

For a ∈ {0} ∩ Θa (u, n), by Eb1 ,a,u

1,{1,2,...,n−1}

and ξi−1

, we have

i = 1, b1 = 0,
1,{1,2,...,n−1}

implying that Eb1 ,a,u

(37)

2,{n+1,n+2,...,N }

does not happen; by Eb2 ,u−a−1,u

2,{1,2,...,n}

and ξi

, we have

b2 ≤ K − i − a − 1.

(38)

By (37), (38) and (31), we have
e b (i, u, n, a) = {(b1 , b2 , b3 ) : b1 = 0, b2 ∈ {u − 1, . . . , K − a − 2}, b1 + b2 + b3 = K}
Θ

(39)

for a ∈ {0} ∩ Θa (u, n).
•

1,{1,2,...,n−1}

For a ∈ {u − 1} ∩ Θa (u, n), by Eb1 ,a,u

1,{1,2,...,n−1}

and ξi−1

, we have

i = K − u, b2 = 0,
2,{n+1,n+2,...,N }

implying that Eb2 ,u−a−1,u

2,{n+1,n+2,...,N }

does not happen; by Eb2 ,u−a−1,u
b1 ≤ a + i − 1.

(40)
2,{1,2,...,n}

and ξi

, we have
(41)

By (40), (41) and (31), we have
e b (i, u, n, a) = {(b1 , b2 , b3 ) : b1 ∈ {u − 1, . . . , K − u + a − 1}, b2 = 0, b1 + b2 + b3 = K}
Θ

(42)

for a ∈ {u − 1} ∩ Θa (u, n).

24

By (33), (36), (39) and (42), we have
1,{1,2,...,n−1}

ξi−1
=

2,{1,2,...,n}

∩ ξi

∩ Eu

[

[

e b (i,u,n,a)
a∈{1,...,u−2}∩Θa (u,n) (b1 ,b2 ,b3 )∈Θ

[
[




[

[

e b (i,u,n,a)
a∈{0}∩Θa (u,n) (b1 ,b2 ,b3 )∈Θ




[

[



2,{n+1,n+2,...,N }

Eb2 ,u−a−1,u

e b (i,u,n,a)
a∈{u−1}∩Θa (u,n) (b1 ,b2 ,b3 )∈Θ

Based on (43), we have
X
′
Pi,u,n
=



1,{1,2,...,n−1}
2,{n+1,n+2,...,N }
3,{n}
Eb1 ,a,u
∩ Eb2 ,u−a−1,u
∩ EK−b1−b2 ,1,u




3,{n}
∩ EK−b2 ,1,u 




1,{1,2,...,n−1}
3,{n}
Eb1 ,a,u
∩ EK−b1 ,1,u  .

X

!

X

a∈{1,...,u−2}∩Θa (u,n) b1 ∈{a,...,i+a−1} b2 ∈{u−a−1,...,K−i−a−1}



(43)

K
b1 , K − b1 − b2 , b2



i
h
1,{1,2,...,n−1}
2,{n+1,n+2,...,N }
3,{n}
× Pr Eb1 ,a,u
∩ Eb2 ,u−a−1,u
∩ EK−b1 −b2 ,1,u


i
h
X
X
K
2,{n+1,n+2,...,N }
3,{n}
Pr Eb2 ,u−a−1,u
∩ EK−b2,1,u
+
b2
a∈{0}∩Θa (u,n) b2 ∈{u−1,...,K−a−2}
  h
i
X
X
K
1,{1,2,...,n−1}
3,{n}
(44)
Pr Eb1 ,a,u
∩ EK−b1,1,u ,
+
b1
a∈{u−1}∩Θa (u,n) b1 ∈{u−1,...,K−u+a−1}

K
where b1 ,K−b1−b2 ,b2 is the total number of partitions of K balls into three parts with the numbers

is the total number of partitions of K balls into two
of balls b1 , b2 and K − b1 − b2 , K
b2

is the total number of partitions of
parts with the numbers of balls b2 and K − b2 , and K
b1
K balls into two parts with the numbers of balls b1 and K − b1 . To calculate (44), we first
i
h
1,{1,2,...,n−1}
2,{n+1,n+2,...,N }
3,{n}
calculate Pr Eb1 ,a,u
∩ Eb2 ,u−a−1,u
∩ EK−b1 −b2 ,1,u for all a ∈ {1, . . . , u−2}∩Θa (u, n),

b1 ∈ {a, a + 1, . . . , i + a − 1} and b2 ∈ {u − a − 1, u − a, . . . , K − i − a − 1}. By using results
from “balls into bins” problem, we have
i
h
1,{1,2,...,n−1}
2,{n+1,n+2,...,N }
3,{n}
Pr Eb1 ,a,u
∩ Eb2 ,u−a−1,u
∩ EK−b1−b2 ,1,u
i
i h
h
2,{n+1,n+2,...,N } 1,{1,2,...,n−1}
1,{1,2,...,n−1}
Eb1 ,a,u
Pr Eb2 ,u−a−1,u
= Pr Eb1 ,a,u
h
i
3,{n}
1,{1,2,...,n−1}
2,{n+1,n+2,...,N }
× Pr EK−b1 −b2 ,1,u Eb1 ,a,u
,
∩ Eb2 ,u−a−1,u

where

i
h
X
1,{1,2,...,n−1}
=
Pr Eb1 ,a,u

X

L1 ∈La,1 (αn′ )n′ ∈L ∈Ab1 ,L1
1

Q

b1 !

n′ ∈L1

αn ′ !

Y

n′ ∈L1

(45)

α

Pn′n′ ,

25

h
i
X
2,{n+1,n+2,...,N } 1,{1,2,...,n−1}
Pr Eb2 ,u−a−1,u
=
Eb1 ,a,u

X

L2 ∈La,2 (αn′ )n′ ∈L ∈Ab2 ,L2
2

Q

Y

b2 !

n′ ∈L2

αn′ ! n′ ∈L

α

Pn′n′ ,

2

h
i
3,{n}
1,{1,2,...,n−1}
2,{n+1,n+2,...,N }
Pr EK−b1 −b2 ,1,u Eb1 ,a,u
= PnK−b1 −b2 .
∩ Eb2 ,u−a−1,u
i
h
2,{n+1,n+2,...,N }
3,{n}
Next, we calculate Pr Eb2 ,u−a−1,u
, EK−b2,1,u for all a ∈ {0} ∩ Θa (u, n), b1 = 0, and

b2 ∈ {u − 1, . . . , K − a − i − 1}. By using results from “balls into bins” problem, we have
i
i h
i
h
h
2,{n+1,n+2,...,N }
3,{n}
2,{n+1,n+2,...,N }
2,{n+1,n+2,...,N }
3,{n}
, (46)
Pr EK−b2 ,1,u Eb2 ,u−a−1,u
Pr Eb2 ,u−a−1,u
∩ EK−b2,1,u = Pr Eb2 ,u−a−1,u
where

i
h
X
2,{n+1,n+2,...,N }
=
Pr Eb2 ,u−a−1,u

X

L2 ∈L0,2 (αn′ )n′ ∈L ∈Ab2 ,L2
2

and

Q

b2 !
n′ ∈L2 αn′ !

Y

α

Pn′n′ ,

n′ ∈L2

h
i
3,{n}
2,{n+1,n+2,...,N }
Pr EK−b2,1,u Eb2 ,u−a−1,u
= PnK−b2 .
i
h
1,{1,2,...,n−1}
3,{n}
Finally, we calculate Pr Eb1 ,a,u
∩ EK−b1,1,u for all a ∈ {u − 1} ∩ Θa (u, n), b2 = 0 and
b1 ∈ {u − 1, . . . , a + i − 1}. By using results from “balls into bins” problem, we have
i
i h
i
h
h
1,{1,2,...,n−1}
3,{n}
1,{1,2,...,n−1}
1,{1,2,...,n−1}
3,{n}
,
Pr EK−b1 ,1,u Eb1 ,a,u
Pr Eb1 ,a,u
∩ EK−b1 ,1,u = Pr Eb1 ,a,u

where

i
h
1,{1,2,...,n−1}
=
Pr Eb1 ,a,u

X

X

L1 ∈Lu−1,1 (αn′ )n′ ∈L ∈Ab1 ,L1
1

Q

b1 !

n′ ∈L1

i
h
1,{1,2,...,n−1}
3,{n}
= PnK−b1 .
Pr EK−b1 ,1,u Eb1 ,a,u

αn ′ !

Y

(47)

α

Pn′n′ ,

n′ ∈L1

′
Substituting (45), (46) and (47) into (44), we can obtain Pi,u,n
given in (12)-(15). Therefore, we

complete the proof of Lemma 1.
A PPENDIX B: P ROOF

OF

L EMMA 2

By (5) and (17), it can be easily shown that the constraints in (1), (2) and (3) of Problem 1 can
be converted into (18), (19) and (20). Now, we show that the objective function of Problem 1

26

in (4) can be converted into the objective function of Problem 3. By (5) and (17), we have
Ravg (K, N, M, x)
! K
K
Y
X
(a) X
=
pdk
d∈N K

=

K  
X
K
s=1

=

k=1

K−1
X
s=0

s

X

zs−1 −

s=1 S∈{S⊆K:|
b
b
S|=s}

min{K,N }

zs−1 −

X
u=1

X

d∈N K

K
Y

k=1

pdk

!

K
X

X

zs−1

s=1 S∈{S⊆K\K(d):|
b
b
S|=s}


K 
X
K −u
Pr [|K(D)| = u]
zs−1
s
s=1


min{K,N }
K−u−1
X K − u
X
K
′′
zs ,
zs −
Pu
s
+
1
s+1
s=0
u=1

(48)

where (a) is due to (5) and (17). Therefore, we complete the proof of Lemma 2.
A PPENDIX C: P ROOF

OF

L EMMA 3

The Lagrangian of Problem 3 is given by
L(z, η, θ, ν)
!
min{K,N }
K  
K
K−u−1
K−1
X
X
X K − u
X K 
X
KM
K
szs −
ηs (−zs ) + θ
zs +
zs −
Pu′′
=
s
s+1
s+1
N
s=0
s=0
s=0
s=0
u=1
!
K  
X
K
zs ,
+ν 1 −
s
s=0

where ηs ≥ 0 is the Lagrange multiplier associated with (18), ν is the Lagrange multiplier
associated with (19), θ is the Lagrange multiplier associated with (20) and η , (ηs )s∈{0,1,...,K}.
Thus, we have
∂L
(z, η, θ, ν) =
∂zs

 min{K,N
 
 
X } K − u
K
K
K
′′
.
−
−ν
− ηs + θs
Pu
s
s+1
s
s
+
1
u=1



(49)

Since Problem 3 is a linear programming, z∗ is an optimal solution of Problem 3 if z∗ , η ∗ , ν ∗ , θ∗
satisfy KKT conditions, i.e., (i) primal constraints: (18), (19), (20), (ii) dual constraints: (a) θ ≥ 0
and (b) ηs ≥ 0 for all s ∈ {0, 1, . . . , K}, (iii) complementary slackness: (a) ηs (−zs ) = 0 for

P

K
K
∂L
KM
= 0, and (iv) ∂z
(z, η, θ, ν) = 0 for all
sz
−
all s ∈ {0, 1, . . . , K} and (b) θ
s
s=0 s
N
s

s ∈ {0, 1, . . . , K}. In the following, we obtain z∗ , η ∗ , ν ∗ , and θ∗ by considering three cases.
Case 1: When M = 0, it can be easily verified that z∗ given in (22), any






 
K 


min{K,N
X } u Ks + K−u
− s+1
s+1

, 0 , +∞ ,
θ∗ ∈ max
max
Pu′′
K
 
s∈{1,2,...,K} 
s s
u=1

27
min{K,N }

X

∗

ν =

Pu′′ u,

u=1

min{K,N }

ηs∗

=

X

Pu′′

u=1




 
 
  
K
K
K−u
K
∗
+θ s
+
−
−u
s
s+1
s+1
s

satisfy the KKT conditions in (i)-(iv). Thus, we know that when M = 0, z∗ given in (22) is an
optimal solution of Problem 3.
Case 2: When M = N, it can be easily verified that z∗ given in (22), any






}
K
K−u
K
min{K,N

X
u
+
−
s+1
s+1
,

θ∗ ∈ 0,
min
Pu′′ s
K

s∈{0,1,...,K−1} 
s
s
u=1
ν ∗ = Kθ∗ ,
 
 min{K,N

X } K − u
K
K
∗
′′
∗
+ θ (s − K)
Pu
−
ηs =
s
s+1
s+1
u=1

satisfy the KKT conditions in (i)-(iv). Thus, we know that when M = N, z∗ given in (22) is an
optimal solution of Problem 3.
n
o
(K−1)N
N 2N
Case 3: When any M ∈ K , K , . . . , K
, we prove that z∗ given in (22) is an optimal

solution of Problem 3 by proving that z∗ given in (22),
min{K,N }
∗

θ =−

X

Pu′′

u=1

min{K,N }
∗

ν =

X

Pu′′

u=1

ηs∗

  min{K,N
X }
K
Pu′′
=
s
u=1

K
X

k=K−u+1

K
X

k=K−u+1

gk′



KM
N



,

(50)

 




KM
KM KM
′
gk
− gk
,
N
N
N
k=K−u+1
K
X

(51)


 




KM
KM
KM
′
gk (s) − gk
+ gk
s−
,
N
N
N
s ∈ {0, 1, . . . , K}, (52)

satisfy the KKT conditions in (i)-(iv), where

QK−k
(K−s−i)

hk (s) , Qi=0
, s ∈ [0, k)
K−k
j=0 (K−j)
, k ∈ {K − u + 1, . . . , K}.
gk (s) ,

0,
s ∈ [k, K]

(53)

In the following, we show that z∗ in (22), θ∗ in (50), ν ∗ in (51), and η ∗ in (52) satisfy KKT
conditions (i), (ii), (iii), and (iv), respectively.

28

•

Prove that z∗ satisfies (i). By substituting z∗ into the primal constraints in (18), (19) and
(20), we can easily verify that z∗ satisfies (i). Thus, we complete proving that z∗ satisfies
(i).

•

Prove that θ∗ satisfies (ii.a) and η ∗ satisfies (ii.b). First, we show that θ∗ satisfies (ii.a) by

proving gk′ KM
≤ 0. Since
N

QK−k
(K−s−i) PK−k

1
h′k (s) = − Qi=0
s ∈ (0, k)
K−k
i=0 K−s−i ,
′
j=0 (K−j)
,
(54)
gk (s) =

0,
s ∈ [k, K)
n
o
(K−1)N
N 2N
′
we have gk (s) ≤ 0 for any s ∈ (0, K). Since M ∈ K , K , . . . , K
, we have

KM
∈ {1, 2, . . . , K − 1}. Therefore, we have gk′ KM
≤ 0. Thus, we complete proving
N
N

that θ∗ satisfies (ii.a). Next, we show that η ∗ satisfies (ii.b) by proving
 




KM
KM
KM
′
gk (s) − gk
+ gk
s−
≥ 0.
N
N
N

(55)

Consider the following four cases.
KM
N

∈ (0, k), (55) is equivalent to





KM
KM
KM
′
hk (s) ≥ hk
+ hk
s−
.
N
N
N

1) When s ∈ [0, k) and

(56)

Since for any convex set X and any two points x, y ∈ X , f (y) ≥ f (x) + f ′(x)(y − x) if and
only if f (x) is convex [22], we prove (56) by proving that 
hk (s) is convex over s ∈ [0, k).
P
2 P
K−k
K−k
1
1
Since h′′k (s) = hk (s)
− i=0 (K−s−i)
≥ 0 for all s ∈ [0, k), by
2
i=0 K−s−i
second-order condition for convexity [22], we know that hk (s) is convex over s ∈ [0, k).

2) When s ∈ [0, k) and

KM
N

∈ [k, K), (55) is equivalent to hk (s) ≥ 0, which holds for all

s ∈ [0, k).
3) When s ∈ [k, K] and

KM
N

∈ (0, k), (55) is equivalent to
K−k
X
i=0

which always holds since
4) When s ∈ [k, K] and

PK−k

KM
N

i=0

s − KM
N
≥ 1,
−i
K − KM
N

s− KM
N
K− KM
−i
N

≥

PK−k
i=0

k− KM
N
K− KM
−i
N

(57)
= 1+

PK−k−1
i=0

k− KM
N
K− KM
−i
N

≥ 1.

∈ [k, K), (55) is equivalent to 0 ≥ 0, which always holds.

Thus, we complete proving that η ∗ satisfies (ii.b).
•

Prove that z∗ , η ∗ satisfies (iii.a) and z∗ , θ∗ satisfies (iii.b). First, we show that z∗ , η ∗ satisfies

(iii.a). Since η ∗KM = 0 and zs∗ = 0 for all s ∈ {0, 1, . . . , K} \ KM
, we know that
N
N

29

•

ηs∗ (−zs ) = 0 for all s ∈ {0, 1, . . . , K}. Thus, we complete proving that z∗ , η ∗ satis ∗
P
K
KM
fies (iii.a). Next, we show that z∗ , θ∗ satisfies (iii.b). Since K
s=0 s szs = N , we have

P
 ∗ KM
K
K
= 0. Thus, we complete proving that z∗ , θ∗ satisfies (iii.b).
θ∗
s=0 s szs − N

Prove that z∗ , η ∗ , ν ∗ and θ∗ satisfies (iv). For any s ∈ {0, 1, . . . , K}, we have

 !
 

min{K,N }
K
X
X
∂L ∗ ∗ ∗ ∗
K
K
−
u
K
.
−
gk (s)
−
Pu′′
(z , η , θ , ν ) =
s
s+1
s+1
∂zs
u=1
k=K−u+1





 PK
k−1
k
k
K
K−u
.
By Pascal’s identity, i.e., k+1
=
+
,
we
have
−
=
k=K−u+1
s
t
t
t−1
s+1
s+1
)
(k−1
Furthermore, for any s ∈ {0, 1, . . . , K}, we have gk (s) = Ks . Therefore, for any s ∈
(s)
∂L
∗
∗ ∗
∗
(z
,
η
,
θ
,
ν
)
=
0.
Thus,
we
complete
proving that z∗ , η ∗ , ν ∗
{0, 1, . . . , K}, we have ∂z
s
and θ∗ satisfies (iv).

Combining the above three cases, we know that z∗ , η ∗ , θ∗ and ν ∗ satisfy the KKT conditions
in (i)-(iv). Therefore, we complete the proof of Lemma 3.
A PPENDIX D: P ROOF

OF

L EMMA 4

Under Conditions 1 and 2, for the simplified problem, the average load, the file partition
constraints, and the cache memory constraint are the same as those of Problem 2. It remains to
transform the subpacketization constraint in (24) in terms of the vector x to (25) in terms of the
vector y. First, by Theorem 1 of [12], the subpacketization constraint in (24) is equivalent to
kxklgst,Fb = kxk1 .

(58)

By the file partition constraint in (2), we have
kxk1 =

K
N X
X

X

xn,S = N.

(59)

n=1 s=0 S∈{S⊆K:|
b
b
S|=s}

By (58) and (59), we have
kxklgst,Fb = N.

(60)

x = W y.

(61)

Next, under Condition 1, it is clear that

Thus, by (60) and (61), we can obtain (25). Therefore, we complete the proof of Lemma 4.

30

A PPENDIX E: P ROOF

OF

L EMMA 5

By Theorem 1 in [20], we know that Problem 5 and Problem 6 have the same optimal solution,
for all

n
o
e
e
Ravg (K, N, M, y0 ) − min Ravg (K, N, M, y) : y ∈ Υ, N ≥ kW yklgst,Fb
n
o
ρ>
min N − kW yklgst,Fb : y ∈ V (Υ), N > kW yklgst,Fb

(62)

with any y0 ∈ Υ and kW y0 klgst,Fb = N. Note that for all y0 ∈ Υ and kW y0 klgst,Fb = N, we
have
eavg (K, N, M, y0 ) ≥ R
e† (K, N, M).
R
avg

(63)

Note that in our case, N = kW yk1 ≥ kW yklgst,Fb always holds, implying that
n
o
e
min Ravg (K, N, M, y) : y ∈ Υ, N ≥ kW yklgst,Fb
n
o
e
e∗ (K, N, M).
= min Ravg (K, N, M, y) : y ∈ Υ = R
avg

(64)

Thus, by (62), (63) and (64), Problem 5 and Problem 6 have the same optimal solution, for all
ρ>

e† (K, N, M) − R
e∗ (K, N, M)
R
avg
avg

n
o.
min N − kW yklgst,Fb : y ∈ V (Υ), N > kW yklgst,Fb

Therefore, we complete the proof of Lemma 5.

A PPENDIX F: P ROOF

OF

L EMMA 6

Let v be an L-dimensional vector. Denote f m (v) , (fjm,v )j∈{1,2,...,L} , where


1, j ∈ {1, . . . , m}
m,v
f[j] =
, m ∈ {1, 2, . . . , L},

0, otherwise

(65)

and [j] represents the index of the j-th largest element in v. By [12], we know that g(y) =
b

b

W T f F (W y) is a subgradient of kW yklgst,Fb . In the following, we first calculate f F (W y). Let
yn[i] ,s[i] denote the i-th largest element in y, where n[i] = ⌊([i] − 1)/(K + 1)⌋ and s[i] = ([i] − 1)

P

i−1
K
+
1
-th to the
mod (K + 1). Since W y is equivalent to x under Condition 1, the
′
i =1 s[i]

31

P
i

i′ =1

K
s[i]



-th largest elements in W y all equal to yn[i] ,s[i] . Thus, the set of the indices of the

Fb-th largest element in W y is


s[i]  
s[i] −1  

X
X
[
K
K
b
+ 1, . . . , n[i] 2K +
n[i] 2K +
ΩF ,W y =
′

s′ 
s
s′ =0
s′ =0
i∈{1,...,I−1}


s[I] −1  
s[I] −1  

I−1 
X
X K
X K
[
K
+ Fb −
.
+ 1, . . . , n[I] 2K +
n[I] 2K +
′
′

s[i] 
s
s
′
′
i=1
b

(66)

s =0

s =0

b

Thus, we have f F (W y) , (fjF ,W y )j∈{1,2,...,N 2K } , where


1, j ∈ ΩFb,W y
Fb,W y
fj
=
.

0, otherwise

(67)

Next, we calculate W T . Let W T , (wm,n )m∈{1,2,...,(K+1)N },n∈{1,2,...,N 2K } . By (26) and (27), we
have









T
W =








JT
JT
·
·
·
JT







,






′
′
where J T , (jm,n
)m∈{1,2,...,(K+1)},n∈{1,2,...,2K } with jm,n
given by



1, Pm−1 K < n ≤ Pm
i=1
i=1
i−1
′
jm,n =

0, otherwise

(68)



K
i−1

.

(69)

Let km , ⌊(m − 1)/(K + 1)⌋ and lm , (m−1) mod (K +1). By (68) and (69), the (lm + 1)-th
row of the (km + 1)-th left-most diagonal block of matrix J T lies in the m-th row of W T . Thus,
for any m ∈ {1, 2, . . . , N(K + 1)}, we have

n

1, n ∈ km 2K + Plm −1
l=0
wm,n =

0, otherwise

K
l



+ 1, . . . , km 2K +

Plm

K
l=0 l

o

.

(70)

32

When m = [i], we have km = n[i] and lm = s[i] . Thus, by (70), we have

n


1, n ∈ n[i] 2K + Ps[i] −1 K + 1, . . . , n[i] 2K + Ps[i]
l=0
l=0
l
w[i],n =

0, otherwise

K
l

o

.

(71)

b

By (67) and (71), we can obtain g(y) = W T f F (W y), indicating (28). Therefore, we complete

the proof of Lemma 6.
R EFERENCES
[1] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Trans. Inf. Theory, vol. 60, no. 5, pp. 2856–2867,
May 2014.
[2] S. Jin, Y. Cui, H. Liu, and G. Caire, “Structural properties of uncoded placement optimization for coded delivery,” CoRR,
vol. abs/1707.07146, 2017.
[3] A. M. Daniel and W. Yu, “Optimization of heterogeneous coded caching,” CoRR, vol. abs/1708.04322, 2017.
[4] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “The exact rate-memory tradeoff for caching with uncoded prefetching,”
CoRR, vol. abs/1609.07817, 2016.
[5] K. Shanmugam, M. Ji, A. M. Tulino, J. Llorca, and A. G. Dimakis., “Finite-length analysis of caching-aided coded
multicasting,” IEEE Trans. Inf. Theory, vol. 62, no. 10, pp. 5524–5537, Oct. 2016.
[6] S. Jin, Y. Cui, H. Liu, and G. Caire, “New order-optimal decentralized coded caching schemes with good performance in
the finite file size regime,” CoRR, vol. abs/1604.07648, 2016.
[7] M. Ji, K. Shanmugam, G. Vettigli, J. Llorca, A. M. Tulino, and G. Caire, “An efficient multiple-groupcast coded multicasting
scheme for finite fractional caching,” in IEEE ICC, Jun. 2015, pp. 3801–3806.
[8] K. Wan, D. Tuninetti, and P. Piantanida, “Novel delivery schemes for decentralized coded caching in the finite file size
regime,” in IEEE ICC Workshops, May 2017, pp. 1183–1188.
[9] L. Tang and A. Ramamoorthy, “Coded caching with low subpacketization levels,” in IEEE Globecom Workshops, Dec.
2016, pp. 1–6.
[10] K. Shanmugam, A. M. Tulino, and A. G. Dimakis, “Coded caching with linear subpacketization is possible using ruzsaszeméredi graphs,” in IEEE ISIT, Jun. 2017, pp. 1237–1241.
[11] M. Cheng, Q. Yan, X. Tang, and J. Jiang, “Coded caching schemes with low rate and subpacketizations,” CoRR, vol.
abs/1708.06650, 2017.
[12] J.-y. Gotoh, A. Takeda, and K. Tono, “Dc formulations and algorithms for sparse optimization problems,” Math
Programming, pp. 1–36, 2017.
[13] P. Flajolet and R. Sedgewick, Analytic combinatorics, 2009.
[14] H. A. Le Thi, T. P. Dinh, H. M. Le, and X. T. Vo, “Dc approximation approaches for sparse optimization,” European
Journal of Operational Research, vol. 244, no. 1, pp. 26–46, 2015.
[15] S. Shalev-Shwartz, N. Srebro, and T. Zhang, “Trading accuracy for sparsity in optimization problems with sparsity
constraints,” SIAM Journal on Optimization, vol. 20, no. 6, pp. 2807–2832, 2010.
[16] W. Fu, “Penalized regressions: The bridge versus the lasso,” Journal of Computational and Graphical Statistics, pp.
397–416, 1998.

33

[17] P. S. Bradley and O. L. Mangasarian, “Feature selection via concave minimization and support vector machines.” in ICML,
vol. 98, 1998.
[18] J. Weston, A. Elisseeff, B. Schölkopf, and M. Tipping, “Use of the zero norm with linear models and kernel methods,” J.
Mach. Learn. Res., vol. 3, pp. 1439–1461, Mar. 2003.
[19] T. Pham Dinh and H. A. Le Thi, “Recent advances in dc programming and dca,” in Trans on Computational Intelligence,
2014, pp. 1–37.
[20] H. A. Le Thi, T. P. Dinh, and H. Van Ngai, “Exact penalty and error bounds in dc programming,” Journal of Global
Optimization, vol. 52, no. 3, pp. 509–535, 2012.
[21] C. Wang, S. H. Lim, and M. Gastpar, “A new converse bound for coded caching,” CoRR, vol. abs/1601.05690, 2016.
[22] S. Boyd and L. Vandenberghe, Convex Optimization.

New York, NY, USA: Cambridge University Press, 2004.

