We consider the problem of monotone, submodular maximization over a ground set of size n subject to cardinality constraint k. For this problem, we introduce streaming algorithms with linearquery complexity and linear number of arithmetic operations ; these algorithms are the first deterministic algorithmsfor submodular maximization that require a linear number of arithmetic operations. Specifically, for any c%DIFDELCMD < \ge %%% 1, \epsilon > 0, we propose a single-pass , deterministic streaming algorithm with ratio 1/(4c)-\epsilon, query complexity \lceil n / c \rceil + c , memory complexity O(k \log k), and O(n) total running time. As k%DIFDELCMD < \to %%% \infty, the ratio converges to (1 - 1/e)/(c + 1).\ge  In addition, we propose a deterministic, multi-pass streaming algorithm with O(1 / \epsilon) passes that achieves ratio 1-1/e - \epsilon in O(n/\epsilon) queries, O(k \log (k)) memory, and O(n) time . We prove a lower bound that implies no constant-factor approximation exists using o(n) queries, even if queries to infeasible sets are allowed. An experimental analysis demonstrates that our algorithms require fewer queries (often substantially less than n) to achieve better objective value than the current state-of-the-art  algorithms.
We consider the problem of monotone, submodular maximization over a ground set of size n subject to cardinality constraint k. For this problem, we introduce the first deterministic algorithms with linear time complexity ; these algorithms are %DIFDELCMD < \ge %%% streaming algorithms. Our single-pass algorithm obtains a constant ratio in \lceil n / c \rceil + c %DIFDELCMD < \to %%% oracle queries, for any c\ge 1. In addition, we propose a deterministic, multi-pass streaming algorithm with a constant number of passes that achieves nearly the optimal ratio with linear query and time complexities . We prove a lower bound that implies no constant-factor approximation exists using o(n) queries, even if queries to infeasible sets are allowed. An empirical analysis demonstrates that our algorithms require fewer queries (often substantially less than n) yet still achieve better objective value than the current state-of-the-art algorithms, including single-pass, multi-pass, and non-streaming algorithms.
R
streaming algorithms with linearquery complexity and linear number of arithmetic operations
the first deterministic algorithms with linear time complexity
D
the first deterministic algorithmsfor submodular maximization that require a linear number of arithmetic operations. Specifically, for any c
R
1, \epsilon > 0, we propose a
streaming algorithms. Our
R
, deterministic streaming algorithm with ratio 1/(4c)-\epsilon, query complexity
algorithm obtains a constant ratio in
D
, memory complexity O(k \log k), and O(n) total running time. As k
R
\infty, the ratio converges to (1 - 1/e)/(c + 1).
oracle queries, for any c
A
1.
R
O(1 / \epsilon)
a constant number of
R
ratio 1-1/e - \epsilon in O(n/\epsilon) queries, O(k \log (k)) memory, and O(n) time
nearly the optimal ratio with linear query and time complexities
R
experimental
empirical
R
to
yet still
A
algorithms, including single-pass, multi-pass, and non-streaming