One can show, by using the same argument as in Lemma REF  of the Appendix, that the objective Eq.  REF is submodular in addition to being normalized and monotone non-decreasing.
It follows that Eq.  REF is a classical submodular set cover problem for which a greedy algorithm maximizing \(f_{\gamma ,\varepsilon }\)  and stopping when \(f_{\gamma ,\varepsilon }({S}_K) = f_{\gamma ,\varepsilon }({M})\)  will always find, up to a logarithmic factor, the minimum possible number of sensors [1]}.
In particular, suppose that \({S}^*\)  is a subset of minimum size with \(f_{\gamma ,\varepsilon }({S}^*) = f({M})\)  and that the greedy algorithm chooses a sequence of subsets \({S}_1, \ldots , {S}_K\)  with \(f_{\gamma ,\varepsilon }({S}_K) = f_{\gamma ,\varepsilon }({M})\) .
If we define the “increment condition number” to be the ratio of the largest and smallest increments in the objective during greedy optimization
\(\kappa = \frac{f_{\gamma ,\varepsilon }({S}_1)}{f_{\gamma ,\varepsilon }({S}_K) - f_{\gamma ,\varepsilon }({S}_{K-1})},\) 
