Since each objective function \(f\)  presented in Section  is submodular, it is possible to use an “accelerated greedy” (AG) algorithm to obtain the same solution as the naive greedy algorithm with a provably minimal number of objective function evaluations compared to a broad class of algorithms [1]}.
Let the increase in the objective function obtained by adding the sensor \(j\)  to the set \({S}\)  be called \(\Delta _j({S}) = f({S}\cup \lbrace j\rbrace ) - f({S})\) .
Instead of evaluating \(\Delta _j({S}_{k-1})\)  for every measurement in \({M}\setminus {S}_{k-1}\) , AG keeps track of an upper bound \(\hat{\Delta }_j \ge \Delta _j({S}_{k-1})\)  on the increments for each sensor.
Since submodularity of \(f\)  means that the increments \(\Delta _j({S})\)  can only decrease as the size of \({S}\)  increases, it is sufficient to have the maximum upper bound \(\hat{\Delta }_{j^*} \ge \hat{\Delta }_{j}\) , \(\forall j\in {M}\setminus {S}_{k-1}\)  be tight \(\hat{\Delta }_{j^*} = \Delta _{j^*}({S}_{k-1})\)  in order to conclude that \(\Delta _{j^*}({S}_{k-1})\)  is the largest increment.
The rest of the upper bounds on the increments can remain loose since they are smaller than the tight maximum upper bound.
The AG algorithm finds largest upper bound \(\hat{\Delta }_{j^*}\)  and updates it so that it is tight.
If \(\hat{\Delta }_{j^*}\)  is still the greatest upper bound, then \(j^* = j_k\)  achieves the largest increment and is added to \({S}_{k-1}\) .
Otherwise if \(\hat{\Delta }_{j^*}\)  is no longer the largest upper bound, the new largest upper bound is selected and process repeated until a tight maximum upper bound is obtained.
