## Part B: Network Design for Energy Optimization
### A way to compute near optimal FMDs  
From the above formulation, the Optimal FMD problem is actually the following \"AT-LEAST-3-SET-COVER\" problem:  
AT-LEAST-3-SET-COVER (\(\geq 3 SC\)): Given \(D=(\Sigma_{1},\ldots,\Sigma_{q})\) where each \(\Sigma_{i}\subseteq U\) (and the union of all \(\Sigma_{i}\) is \(U\)) and given the costs \(c(\Sigma_{i})\geq 0\), select a minimum total cost sub-collection \(F\) of \(D\) so that each element \(e\) in \(U\) belongs to (is \"covered\" by) at least 3 sets in \(F\). _Important note:_ Note that geometry and geometric covers can not help here because the domain since \(S\) is a complicated 3D domain that can be highly irregular; also, the timing parts of the elements escape the Cartesian geometry; finally, the cost of each \(\Sigma_{i}\) is a complicated function of placement decisions of sensors of various capabilities. The problem of \(\geq 3 SC\) is NP-hard. This is so, since the usual min-cost SET-COVER problem can be reduced to it by adding to any instance of SET-COVER two sets of zero cost, each covering all elements. We now describe a formulation of the problem as an integer linear program and give an approximate solution based on randomized rounding. Note that our method can be extended to low cost \"SET-COVER by a at least \(l\) sets\" (let us denote this problem as \(\geq l\)-SET-COVER) if the redundancy of \(l>3\) is needed to make the _redundant monitoring decision_\(D\) easier to construct and fault-tolerant. We remind the reader of the computational complexity of set covering problems: [PERSON] and [PERSON] showed in 1994 that set cover cannot be approximated in polynomial time to within a logarithmic factor, unless NP has quasi-polynomial time algorithms [33]. [PERSON] improved their inapproximability lower bound, under the same assumptions, giving a slightly better bound that essentially matches the approximation ratio achieved by the greedy algorithm [17]. [PERSON], [PERSON], and [PERSON] established a larger lower bound, under the weaker assumption that P \(\
eq\) NP [2]. The \(k\)-set cover problem is a variant in which every set is of size bounded by \(k\). While \(k\)-set cover problem can be solved in polynomial time (via matchings) for \(k=2\), it is NP-complete and even MAX SNP-hard for \(k\geq 3\). Greedy algorithms in that case achieve an approximation ratio of \(\ln k+\Theta(1)\). Hardness results show that it is not approximable within \((1-\epsilon)\ln n\), under strong complexity-theoretic evidence [17]. For 3-set cover, besides linear programming techniques (fractional covers), also local and \"semi-local\" approximation techniques have been used e.g. in [14, 20, 21]. The randomized rounding method  
For set \(\Sigma\) let \(x(\Sigma)\) be 1 if \(\Sigma\) is selected and 0 else. We want to  
\[\text{minimize }\sum_{\Sigma\text{ in }D}x(\Sigma)\cdot c(\Sigma)\]  
subject to  
(1) \(x(\Sigma)\in\{0,1\}\)  
(2) Let \(E(e)\) be the collection of all \(\Sigma\) containing element \(e\). Then, for each element \(e\),  
\[\sum_{\Sigma\text{ in }E_{e}}x(\Sigma)\geq 3\]  
Let IP1 be the above integer linear program. We relax the above integer program to the following linear program (LP1):  
\[\text{minimize }\sum_{\Sigma\text{ in }D}x(\Sigma)c(\Sigma)\]  
given that  
\((1)\forall\Sigma,0\leq x(\Sigma)\leq 1\)  
\((2)\)\(\forall e,\sum_{\Sigma\text{ in }E(e)}x(\Sigma)\geq 3\)  
Let \(\{p(\Sigma)\}\) be the optimal solution to the above (i.e. \(x(\Sigma)=p(\Sigma)\) get the minimum). We can find \(\{p(\Sigma)\}\) in polynomial time in the size \(n\) of the redundant monitoring decision \(D\). We then form a subcollection of sets as follows:  
Initially \(C=\emptyset\)  
_Experiment E._  
For each \(\Sigma\) in \(D\), put \(\Sigma\) into the sub-collection \(C\) with probability \(p(\Sigma)\), independently of the others. The experiment \(E\) above outputs a sub-collection \(C\).