For the problem of maximizing a nonnegative, (not necessarily monotone) submodular function with respect to a cardinality constraint, we propose deterministic algorithms with linear time complexity; these are the first algorithms to obtain constant approximation ratio with high probability in linear time. Our first algorithm is a single-pass streaming algorithm that obtains ratio 9.298 + $\epsilon$ and makes only two queries per received element. Our second algorithm is a multi-pass streaming algorithm that obtains ratio 4 + $\epsilon$. Empirically, the algorithms are validated to use fewer queries than and to obtain comparable objective values to state-of-the-art algorithms.

翻译：对于使非负性、(不一定是单质)亚模式功能在基本限制方面最大化的问题,我们建议采用具有线性时间复杂性的确定式算法;这是在线性时间里获得常近似比率且概率高的第一种算法。我们的第一种算法是获得9.298 + $\ epsilon + $ epsilon + $ epsilon 的单行流算法,每个接收元素只进行两次查询。我们的第二种算法是获得4 + $\ epsilon 的多行流算法。典型地说,这些算法被验证为使用查询次数少于和获得与最新算法可比的客观数值。