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 (13γ2? )-approximation algorithm with the memory O(klog2(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 (12γ? ) through the sub-windows at the expense of losing some memory. Our results generalize the corresponding results for the submodular case.