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) -approximate deterministic algorithm with linear query complexity , which performs O(n / \varepsilon) queries. To the best of our knowledge, this is the first deterministic algorithm that achieves the almost optimal approximation and optimal query complexity simultaneously. Query complexity lower bound of submodular maximization problems is also studied in this paper. We show that there exists no (randomized) (1/4+\varepsilon)-approximate algorithm using o(n/\log n) queries for unconstrained submodular maximization. Combining with existing results, we present a complete characterization of the query complexity of unconstrained submodular maximization .