# Multi-Connectivity for Multicast Video Streaming in Cellular Networks
## 5 Centralized Greedy Approximation Algorithm
### Comparison with Optimal Solutions  
In this section, we evaluate the performance guarantees of the proposed CGA algorithm by comparing its solution with the optimal solution obtained for a smaller sized problem of the form in Definition 1. For the purposes of this comparison, we use a 3-cell MC multicast system with 5 PRBs in each cell. To obtain the optimal solution, we employ a brute force algorithm that works as follows. The brute force algorithm first lists out all the possible PRB allocations for the 3-cell system. For instance, for a system with 2 cells and 2 PRBs, denoted by \(p_{1}\) and \(p_{2}\) in each cell, the possible allocations would be \((p_{1},p_{1}),(p_{1},p_{2}),(p_{2},p_{1}),\) and \((p_{2},p_{2})\). Following this, the algorithm finds the total number of UEs that would be served under each of these possible allocations. Finally, the output of the algorithm is the allocation that serves the maximum number of UEs.  
In Figure 1(a),b, we plot the number of UEs left unserved under the CGA algorithm and the corresponding optimal value obtained using the brute force algorithm. We refer to the plot corresponding to the brute force algorithm as 'Optimal' in the figures. Figure 1(a) shows the number of UEs left unserved under the two algorithms as a function of an increasing number of UEs in the system. We observe that the solution of the CGA algorithm matches the optimal solution for up to 30 UEs in the system. As the number of UEs increases, up to 3 additional UEs are left unserved while using the CGA algorithm compared to the optimal solution. Figure 1(b) shows the number of UEs left unserved under the two algorithms as a function of increasing cell sizes. We observe that CGA serves just as many UEs as the optimal solution for smaller cell sizes. As the cell sizes increase, one additional UE is left unserved under the CGA algorithm compared to the optimal solution.  
These plots show that the CGA algorithm provides optimal solutions for smaller systems. However, as the scale of the system increases, the solution provided by the CGA algorithm becomes sub-optimal.  
Figure 2: Comparisons of the average number of users left unserved under CGA and the optimal resource allocation as a function of (**a**) an increasing number of users and (**b**) increasing cell radii (number of users \(=10\)).  
Although the CGA algorithm provides provable approximation guarantees, it does so while requiring the presence of a central controller that can make allocation decisions for all base stations, based on the global view of the system. As the number of cells \(C\) increases, such a centralized setup may lead to large communication overheads and increased delays. In this case, a decentralized approach where base stations make allocation decisions independently might be more feasible, albeit at the cost of losing on the performance of the MC multicast streaming. In the following, we discuss the performance trade-offs between the centralized and distributed allocation for MC multicasting and propose a distributed approximation algorithm for \(\mathbf{K}^{\star}\).