Approximation Algorithms for Non-Submodular Optimization Over Sliding Windows.

In this paper, the problem we study is how to maximize a monotone non-submodular function with cardinality constraint. Different from the previous streaming algorithms, this paper mainly considers the sliding window model. Based on the concept of diminishing-return ratio γ , we propose a (1 3 γ 2 −) -approximation algorithm with the memory O (k log 2 (k Φ 1 γ) 2 ) , where Φ is the ratio between maximum and minimum values of any singleton element of function f. Then, we improve the approximation ratio to (1 2 γ −) through the sub-windows at the expense of losing some memory. Our results generalize the corresponding results for the submodular case. [ABSTRACT FROM AUTHOR]