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: In this work, we present the first linear query complexity algorithm for maximizing a monotone submodular function subject to a cardinality constraint, which achieves the approximation ratio of (1-1/e-\varepsilon) -approximate deterministic algorithm with linear query complexity , which performs O(n / \varepsilon) queries in total .