In fact, Algorithm 1 of (Biçici and Yuret, 2011) is precisely the accelerated greedy algorithm of (Minoux, 1978) applied to the submodular function corresponding to f (X) = ∑ u∈U f u (X), and Algorithm 1 of (Biçici, 2013) is the cost-normalized variant of this greedy algorithm corresponding to a knapsack constraint (Sviridenko, 2004).
our analysis shows that these methods also have a 1 − 1/e performance guarantee and also the O(n log n) empirical complexity mentioned in Section 2.