Before revision:  these algorithms are the first deterministic algorithmsfor submodular maximization that require a linear number of arithmetic operations. Specifically, for any c 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.
After revision:  these algorithms are  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.