# Two-Layer Network Caching for Different Service Requirements
## 3 Model
### Caching Problems
#### 3.3.2 Case 2: Variable-Size Items
```
1:functionAlgorithm2 bis(\(\Xi,size(m)\forall m\in\Xi,\Phi,\mathbf{D}\), \(K_{2}\), \(\{\lambda_{i}\}\))\(\rightarrow\)\(\varepsilon_{j}\)
2:\(\varepsilon_{j}\leftarrow\varnothing\quad\forall i,j\)\(\triangleright\) initialization
3:\(step\gets 1\)
4:\(T_{j}\gets 0\quad\forall j\)\(\triangleright\) thresholds on the cache occupation
5:\(d(m,i)\gets d(m,i)\lambda_{i}\quad\forall i\)
6:while\((\exists j:T_{j}<K_{2,j})\wedge(step\leq C)\)do\(\triangleright\) core of the greedy algorithm
7:\(m^{*}\), \(\{j^{*}\}\leftarrow\textsc{Procedure1}(\Phi,\mathbf{D},\mathbf{T},|K2|,\Xi)\)
8: step \(\leftarrow\) step+1
9:\(\varepsilon_{j^{*}}\leftarrow\varepsilon_{j^{*}}\cup\{m^{*}\}\)
10: cache \(m^{*}\) distributing items over \(\{j^{*}\}\) and update \(\mathbf{T}\)
11:endwhile
12:return\(\varepsilon_{j}\)
13:endfunction
1:functionProcedure1(\(\Phi,\mathbf{D},\mathbf{T},|K_{2}|,\Xi)\)\(\rightarrow\)\(m^{*}\), \(\{j^{*}\}\)
2:\(\{m^{+}\}\)\(\leftarrow\varnothing\), \(\{m^{*}\}\)\(\leftarrow\varnothing\)
3:\(\mathrm{Y}=\Phi^{\mathsf{T}}\mathbf{D}\)
4:while\(\mathrm{Y}\
eq[0]\)do
5:\(\{m^{+}\}\gets argmax_{m}(\mathrm{Y})\)
6:for all\(m\in\{m^{+}\}\)do\(\triangleright\) check if sufficient cache storage is available
7:\(L_{m}\gets 0\)\(\triangleright\) space available for content \(\xi\) in caches
8:for all\(j\in\{j:(j,m^{+})=max(\mathrm{Y})\}\)do
9:\(L_{m}\gets L_{m}+K_{2,j}-T_{j}\)
10:if\(L_{m}\geq size(m)\)then
11:\(\{m^{*}\}\gets m\)
12:endif
13:endfor
14:endfor
15:\(m^{*}\)\(=\) max-size \(\{m^{*}\}\), \(\{j^{*}\}\leftarrow\{j:(j,m^{*})=max(\mathrm{Y})\}\)
16:return\(m^{*}\), \(\{j^{*}\}\)
17:if\(\{m^{*}\}=\varnothing\)then\(\triangleright\) descrease the max \(\mathrm{Y}=\Phi^{\mathsf{T}}\mathbf{D}\)
18:\(\mathrm{Y}(m^{+},\{j\in(j,m^{+})=max(\Phi^{\mathsf{T}}\mathbf{D})\})\gets 0\)\(\triangleright\) values corresponding to
19:\(newmax\leftarrow\max_{m}\mathrm{Y}(m^{+},:)\)\(\triangleright\) the \(m^{+}\) columns to the
20:\(\mathrm{Y}(m^{+},\{j\in(j,m^{+})\})\gets newmax\)\(\triangleright\) second largest ones
21:endif
22:endwhile
23:return\(\varnothing,\varnothing\)\(\triangleright\) no solution found
24:endfunction
```  
**Code 3** Solution to Problem 5. Procedure1 in Code 3 searches for the maximum density of popularity value for the uncached contents (row 4). If some identified contents in \(\{m^{+}\}\) are large enough to be stored in caches reachable by users that generate the maximum density of popularity, the largest content is returned together with the caches where it can be stored (row 16). Otherwise a particular management is necessary, which is the peculiar part of Procedure1. It is the management of the matrix \(\mathrm{Y}\) when the size of the selected contents \(\{m^{+}\}\) is greater than the room available in the identified caches that optimize the overall score. In this case, the density of popularity of these contents is reduced to the second score value of the columns indexed by \(\{m^{+}\}\). In this way, the number of caches that can be used increases, and the content could be allocated in the following iteration. If no contents are selected, empty sets are returned (row 23). The computational cost of the procedure is determined by the iterated maximum search in \(\mathrm{Y}=[|K_{2}|\times C]\), which is linear with the size of \(\mathrm{Y}\), since all the other operations require a lower effort. It multiplies with the complexity of Algorithm2. The result is the price to pay for caching entire items in chunks in a greedy way in different caches. For what concerns the approximation ratio, note that constraints of Problems 4 and 5 clearly define uniform matroids (see Appendix A). The submodular maximization function is the same as in Problem 3. Following the same steps of the proof relevant to Algorithm1, it is easy to find that the achievable approximation ratio it is the same as for Algorithm1.