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 .
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) using 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 .
R
We show that for the cardinality constrained monotone submodular maximization problem, there exists a
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
R
-approximate deterministic algorithm with linear query complexity , which performs O(n
using O(n
R
\varepsilon) queries in total
\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