A new greedy strategy for maximizing monotone submodular function under a cardinality constraint

In this paper, we study the problem of maximizing a monotone non-decreasing submodular function $$f :2^\Omega \rightarrow {\mathbb {R}}_{+}$$ f : 2 Ω → R + subject to a cardinality constraint, i.e., $$\max \{ f(A) : |A| \le k, A \subseteq \Omega \} $$ max { f ( A ) : | A | ≤ k , A ⊆ Ω } . We propose a deterministic algorithm based on a new greedy strategy for solving this problem. We prove that when the objective function f satisfies certain assumptions, the algorithm we propose can return a $$1 - \kappa _f (1 - \frac{1}{k})^k$$ 1 - κ f ( 1 - 1 k ) k approximate solution with O(kn) value oracle queries, where $$\kappa _f$$ κ f is the curvature of the monotone submodular function f. We also show that our algorithm outperforms the traditional greedy algorithm in some cases. Furthermore, we demonstrate how to implement our algorithm in practice.