Before revision: We show that for the cardinality constrained monotone submodular maximization problem, there exists a (1-1/e-\varepsilon) -approximate deterministic algorithm with linear query complexity , which performs O(n / \varepsilon) queries in total .
After revision: We show that for the cardinality constrained monotone submodular maximization problem, there exists a (1-1/e-\varepsilon) using O(n / \varepsilon) queries in total .