# Multi-Connectivity for Multicast Video Streaming in Cellular Networks
## 5 Centralized Greedy Approximation Algorithm  
We propose a greedy approximation algorithm for solving the resource allocation problem \(\mathbf{K}^{\star}\). Centralized greedy approximation (CGA) works iteratively by maximizing the number of additional users served in each iteration. In the first iteration, the CGA chooses the set \(U_{jc}\) of the form in (1) from \(\mathcal{U}\) that has the largest number of elements. In the subsequent steps, it picks a \(U_{jc}\) that serves the maximum number of yet unserved users. In each step, the set chosen is from a different sub-collection \(\mathcal{U}_{c}\), i.e., \(c\) in the subscript of the chosen sets is different for each set picked by the algorithm. The collection of sets chosen after \(C\) iterations \(\mathcal{U}_{G}\) is the output of the algorithm. The steps involved in the decision making of the CGA policy are explained below. To begin, we have an empty solution set \(\mathcal{U}_{G}\). 1. In the first step of CGA, the algorithm finds the largest set \(U_{j^{\star}c^{\star}}\in\mathcal{U}\), i.e., \((j^{\star},c^{\star})\in\arg\max_{j\in[N],c\in[C]}\{U_{jc}\}\). 2. The solution set \(\mathcal{U}_{G}\) is updated to \(\mathcal{U}_{G}\bigcup\{U_{j^{\star}c^{\star}}\}\). This implies that PRB \(j^{\star}\) is allocated to the multicast stream in cell \(c^{\star}\). 3. Next, for all \(j\in[N]\), the sets \(U_{jc^{\star}}\) are removed from the set \(\mathcal{U}\). This step ensures that the algorithm finds a feasible solution that satisfies the constraint (4) in Definition 1. 4. In the next step, CGA picks the set \(U_{j^{\star}c^{\star}}\in\mathcal{U}\) that contains the maximum number of UEs that were not present in any set \(U_{jc}\) picked in the previous iterations and assigns PRB \(j^{\star}\) to the multicast stream in cell \(c^{\star}\). Following this, steps 2, 3, and 4 are repeated \((C-1)\) times to determine the solution. At the end of \(C\) iterations of CGA, the output set \(\mathcal{U}_{G}\) contains exactly \(C\) sets of the form \(U_{jc}\). The PRB assigned to the multicast stream in cell \(c\) is given by \(j\in[N]\) such that \(U_{jc}\in\mathcal{U}_{G}\). The pseudo-code for this algorithm is given in Algorithm 3. ```
Input: Universe \([M]\), \(\mathcal{U}=\{\mathcal{U}_{1},\ldots,\mathcal{U}_{C}\}\), \(C\) Initialize: \(\mathcal{U}_{G}=\phi\) for\(n=1:C\)do  Pick \(U_{j^{\star}c^{\star}}\in\mathcal{U}\) that covers the maximum number of elements from \([M]\setminus\bigcup_{U_{jc}\in\mathcal{U}_{G}}U_{jc}\) \(\mathcal{U}_{G}\leftarrow\mathcal{U}_{G}\bigcup\{U_{j^{\star}c^{\star}}\}\) \(\mathcal{U}\leftarrow\mathcal{U}\setminus\mathcal{U}_{c^{\star}}\) end for
```  
**Algorithm 3**Centralized Greedy Approximation Algorithm for \(\mathbf{K}^{\star}\)  
In the following theorem, we prove that the solution to \(\mathbf{K}^{\star}\) given by CGA has an approximation factor of \(\left(1-\frac{1}{e}\right)\). This means that _the solution provided by this approximation algorithm serves at least \(\left(1-\frac{1}{e}\right)\) of the number of users that would be served by the optimal algorithm_. To state this result, we first define the following notation. Let \(OPT\) denote the optimal solution to the resource allocation problem \(\mathbf{K}^{\star}\), i.e., the optimal algorithm would serve \(OPT\) UEs in the system. Let \(m_{n}\) denote the number of UEs served up to the \(n\)th iteration by the CGA algorithm. The gap between the optimal solution and the intermediate solution of the CGA algorithm after the \(n\)th iteration is given by  
\[b_{n}=OPT-m_{n}. \tag{7}\]  
Therefore, \(m_{0}=0,b_{0}=OPT\), and the total number of UEs served by the CGA algorithm at the end of \(C\) iterations is given by \(m_{C}\). Using these notations, the following theorem presents the approximation factor for the CGA algorithm. **Theorem 2**. : _The CGA algorithm (Algorithm 3) is a \(\left(1-\frac{1}{e}\right)\) approximation for the resource allocation problem \(\mathbf{K}^{*}\).