obtained by replacing \(\tilde{w}\)  with \(w\)  in Eq.  REF, becomes a normalized, monotone, submodular function on subsets \({S}\subseteq {M}\)  (Lemma REF  in the Appendix) and a simple greedy approximation algorithm guarantees near-optimal performance on this problem!
The greedy algorithm produces a sequence of sets \({S}_1, {S}_2, \ldots \) , by starting with \({S}_0 = \emptyset \)  and adding the sensor \(j_k\)  to \({S}_{k-1}\)  that maximizes the objective \(f_{\gamma }({S}_{k-1}\cup \lbrace j\rbrace )\)  over all \(j\in {M}\setminus {S}_{k-1}\) .
If \({S}^*_K\)  maximizes \(f_{\gamma }({S})\)  over all subsets of size \(\#({S}) = K\)  then the classical result of G. L. Nemhauser et al. [1]} states that the objective values attained by the greedily chosen sets satisfy
\(f_{\gamma }({S}_k) \ge \left(1 - e^{-k/K} \right)f_{\gamma }({S}^*_K), \qquad k=1,\ldots , \#({M}).\) 
