A Note on Monotone Submodular Maximization with Cardinality Constraint
share
We show that for the cardinality constrained monotone submodular maximization problem, there exists a (1-1/e-ε)-approximate deterministic algorithm with linear query complexity, which performs O(n/ε) queries in total.
READ FULL TEXT