# Multi-Connectivity for Multicast Video Streaming in Cellular Networks
## 5 Centralized Greedy Approximation Algorithm
That is,_  
\[m_{\mathrm{C}}\geq\left(1-\frac{1}{e}\right)OPT. \tag{8}\]  
_In fact, no other algorithm can achieve a better approximation unless \(P=NP\)._  
To prove Theorem 2, we first prove the following two results. First, in Lemma 1, we determine the lower bound on the incremental improvements in the solution achieved in the intermediate steps of the CGA algorithm. This result will quantify the rate at which the CGA algorithm approaches the optimal solution. Then, in Lemma 2, we provide an upper bound on \(b_{n}\) that quantifies the gap between the optimal solution \(OPT\) and the intermediate solution of the CGA algorithm at the \(n\)th iteration, \(m_{n}\). Finally, using these two results, we can prove that the solution of the CGA algorithm is at least within \(\left(1-\frac{1}{e}\right)\) of the optimal solution. **Lemma 1**. : _Under the CGA algorithm, the number of additional UEs served from iteration \(n\) to \(n+1\) is lower bounded by \(\frac{b_{n}}{\mathrm{C}}\). That is, for all \(n\geq 0\), it holds that_  
\[m_{n+1}-m_{n}\geq\frac{b_{n}}{\mathrm{C}}, \tag{9}\]  
_where \(\mathrm{C}\) is the total number of cells in the system, and \(b_{n}\) is in (7)._  
Proof. : Let \(U_{OPT}=\{U_{1}^{*},\ldots,U_{\mathrm{C}}^{*}\}\) be the optimal solution of the resource allocation problem \(\mathbf{K}^{*}\), where for all \(c\in[\mathrm{C}]\), the set \(U_{c}^{*}\) is the set of UEs served by the base station of cell \(c\). Let \(M_{n}\) denote the set of users served at the end of the \(n\)th iteration of CGA, and \(M_{n}^{\mathrm{C}}=[M]\setminus\{M_{n}\}\) is the set of users not yet covered at the end of the \(n\)th iteration. Then, it holds that  
\[\sum_{c=1}^{C}\left|U_{c}^{*}\bigcap M_{n}^{\mathrm{C}}\right| \geq\left|\bigcup_{c=1}^{C}\left(U_{c}^{*}\bigcap M_{n}^{\mathrm{ C}}\right)\right| \tag{10}\] \[\geq OPT-m_{n}=b_{n}. \tag{11}\]  
Due to multi-connectivity, the sets \(U_{1}^{*},\ldots,U_{\mathrm{C}}^{*}\) are not disjoint, which implies the inequality in (10). The quantity \(\left|\bigcup_{c=1}^{C}\left(U_{c}^{*}\bigcap M_{n}^{\mathrm{C}}\right)\right|\) on the right hand side of (10) gives the number of unserved UEs after \(n\) iterations that would be served by the optimal solution \(U_{OPT}\). To arrive at the inequality in (11), note that the UEs served by the CGA algorithm may not be the same UEs that the optimal algorithm serves. Therefore, \(\left|\bigcup_{c=1}^{C}\left(U_{c}^{*}\bigcap M_{n}^{\mathrm{C}}\right)\right|\) is at least equal to \(OPT-m_{n}\). From (10) and (11), it follows that  
\[\max_{c\in[\mathrm{C}]}\left|U_{c}^{*}\bigcap M_{n}^{\mathrm{C}}\right| \geq\frac{(OPT-m_{n})}{C} \tag{12}\] \[=\frac{b_{n}}{C}. \tag{13}\]  
Since CGA picks the set that serves the maximum possible number of yet unserved users in each iteration, we have  
\[m_{n+1}-m_{n}\geq\max_{c\in[\mathrm{C}]}\left|U_{c}^{*}\bigcap M_{n}^{ \mathrm{C}}\right|. \tag{14}\]  
From (13) and (14), it follows that  
\[m_{n+1}-m_{n}\geq\frac{b_{n}}{C}, \tag{15}\]which completes the proof. The difference between the number of UEs served in the optimal solution and the number of users served by the at the end of \(n+1\) iterations of the CGA algorithm is upper bounded as follows:  
\[b_{n+1}=OPT-m_{n+1}\leq\left(1-\frac{1}{C}\right)^{n+1}OPT, \tag{16}\]  
where \(m_{n+1}\) denotes the total number of UEs served by the CGA algorithm up to and including the \((n+1)\)th iteration. Proof. : We prove this result by induction. For \(n=0\), if  
\[m_{\mathrm{C}}\geq\left(1-\frac{1}{e}\right)OPT. \tag{8}\]0  
it implies that  
\[m_{\mathrm{C}}\geq\left(1-\frac{1}{e}\right)OPT. \tag{8}\]1  
which is true due to Lemma 1. Thus, the result holds for \(n=0\). Now, we assume that  
\[m_{\mathrm{C}}\geq\left(1-\frac{1}{e}\right)OPT. \tag{8}\]2  
and prove the corresponding inequality for \(b_{n+1}\).