## Part B: Network Design for Energy Optimization
### A way to compute near optimal FMDs
Clearly,  
\[E(cost(C))=\sum_{\Sigma\text{ in }D}c(\Sigma)\mathbb{P}\{\Sigma\text{ is picked}\}=\sum_{\Sigma\text{ in }D}c(\Sigma)p(\Sigma)=OPT_{f}\]  
where \(OPT_{f}\) is the optimal value of the linear program LP1. The found collection \(C\) has a very nice expected cost (even better than what one can achieve in our original _integer_ problem) but we have to examine feasibility. Since we want to get a \(C\) where each \(e\) in \(U\) belongs to at least 3 sets of \(C\), we must examine whether the (random) \(C\) obtained has this property. **Definition 14**: _Let \(\alpha\) be an element in \(U\) and \(C\) obtained by the experiment \(E\). We denote by \(p(\alpha,C)\) the probability that \(\alpha\) belongs to at least 3 sets of \(C\)._  
Let w.l.o.g. \(\Sigma_{1},\ldots,\Sigma_{\lambda}\) be the sets of our RMD containing element \(\alpha\). Here, we must have \(\lambda\geq 3\), else LP1 will report infeasibility. W.l.o.g. denote by \(p_{i}\) the probability \(p\left(\sum_{i}\right)\) obtained via LP1, i.e. that \(\Sigma_{i}\) is chosen to be in \(C\). Assuming that LP1 is feasible we get:  
\[\gamma=p_{1}+\cdots+p_{\lambda}\geq 3 \tag{8}\]  
Let \(A_{3},N_{0},N_{1},N_{2}\) be the events:  
\(A_{3}=``\alpha\) is covered by at least 3 sets in \(C\)\"  
\(N_{0}=``\alpha\) does not belong to any set in \(C\)\"  
\(N_{1}=``\alpha\) belongs to exactly one set in \(C\)\"  
\(N_{2}=``\alpha\) belongs to exactly two sets in \(C\)\"  
Now,  
\[p(\alpha,C)=\mathbf{P}\{A_{3}\}=1-\mathbf{P}\{N_{0}\}-\mathbf{P}\{N_{1}\}- \mathbf{P}\{N_{2}\} \tag{9}\]  
We now estimate \(\mathbf{P}\{N_{i}\}\), for \(i=0,1,2\):  
We will repeatedly use the following fact:  
**Fact (*)** If the numbers \(x_{1},\ldots,x_{\lambda}\) are each in \([0,1]\) and \(x_{1}+\cdots+x_{\lambda}\geq\gamma\), then \((1-x_{1})\cdots(1-x_{\lambda})\leq\left(1-\frac{\gamma}{\lambda}\right)^{\lambda} \leq e^{-\gamma}\) (it is assumed that \(\gamma\leq\lambda\)). Fact (*) can be proved via an easy induction, or via the fact that the arithmetic mean is bigger or equal than the geometric one. **Proof of Fact (*)** Let \(y_{i}=1-x_{i},i=1,\ldots,\lambda\). Then, \(\sum y_{i}=\lambda-\sum x_{i}\leq\lambda-\gamma\). So,  
\[\frac{\sum y_{i}}{\lambda}\leq 1-\frac{\gamma}{\lambda} \tag{10}\]  
But, \(\frac{\sum y_{i}}{\lambda}\geq\sqrt[3]{\pi y_{i}}\) (arithmetic mean vs geometric mean), so:  
\[\frac{\sum y_{i}}{\lambda}\geq\sqrt[3]{(1-x_{1})\cdots(1-x_{\lambda})}\]  
So, by Equation (3), \(\sqrt[3]{(1-x_{1})\cdots(1-x_{\lambda})}\leq 1-\frac{\gamma}{\lambda}\). So, \((1-x_{1})\cdots(1-x_{\lambda})\leq\left(1-\frac{\gamma}{\lambda}\right)^{\lambda}\)\(\diamond\)  
We now have:  
(a) \(\mathbf{P}\{N_{0}\}=(1-p_{1})\cdots(1-p_{\lambda})\). By the Fact (*), then  
\[\mathbf{P}\{N_{0}\}\leq\left(1-\frac{\gamma}{\lambda}\right)^{\lambda}\leq \exp(-\gamma)\]  
Also, by inclusion-exclusion,  
\[\mathbf{P}\{N_{1}\}=p_{1}\cdot\mathbf{P}\{\mbox{no cover of $\alpha$ in the trials of $\Sigma_{2},\ldots,\Sigma_{\lambda}$}\}+\]  
\[\sum_{\Sigma\text{ in }E_{e}}x(\Sigma)\geq 3\]0(because \(p_{2}+\cdots+p_{\lambda}=\gamma-p_{1}\) so \((1-p_{2})\cdots(1-p_{\lambda})\leq\left(1-\frac{\gamma-p_{1}}{\lambda}\right)^{ \lambda}=\exp(-(\gamma-p_{1}))\) and also because \(\mathds{P}\{\)1 success in the trials of \(\Sigma_{2},\ldots,\Sigma_{\lambda}\}\leq\mathds{P}\{N_{1}\;\}\) ). So,  
\[\sum_{\Sigma\text{ in }E_{e}}x(\Sigma)\geq 3\]1  
so  
\[\sum_{\Sigma\text{ in }E_{e}}x(\Sigma)\geq 3\]2  
Similarly,  
\[\sum_{\Sigma\text{ in }E_{e}}x(\Sigma)\geq 3\]3  
\[\sum_{\Sigma\text{ in }E_{e}}x(\Sigma)\geq 3\]4  
also, so \(\mathds{P}\{N_{2}\}\leq\frac{1}{e^{\gamma-1}}\). Thus,  
\[\sum_{\Sigma\text{ in }E_{e}}x(\Sigma)\geq 3\]5  
and \(\gamma\geq 3\). So, \(\mathds{P}\{A_{3}\}=p(a,c)\geq 1-\frac{1}{e^{3}}-\frac{2}{e^{2}}>\frac{1}{2}\). Let \(\xi=1-\frac{1}{e^{3}}-\frac{2}{e^{2}}\).