Approximation Algorithms For Non-Submodular Optimization Over Sliding Windows

This paper mainly studies the problem of maximizing non-submodular functions with cardinality constraints.Unlike the previous insert-only algorithm,this paper mainly designs a bidirectional algorithm that can be inserted and deleted based on the idea of sliding window,which solves the problem that elements are time-sensitive and functions do not meet the submodular property.In the first chapter,the value of the problem studied in this paper is expounded,and the introduction of the problem is foreshadowed,and the definition theorems and symbols involved in the following text are briefly explained.In the second chapter,several widely studied submodular and non-submodular maximization problems are mainly introduced.This paper expounds the emphases,advantages and disadvantages of each kind of problems from different angles,and briefly describes the basic ideas used to solve this kind of problems.In the third chapter,firstly,the problem to be studied in this paper is described.In order to solve the problem well,the idea of sliding window is chosen to filter the expired elements,and then the filtered elements are filtered by the flow screening algorithm to achieve the expected goal.The algorithm is described in detail,and its performance is analyzed from the aspects of approximate ratio,storage complexity and time complexity.In order to obtain a better approximation ratio,we designed a bidirectional sub-window algorithm at the expense of abandoning part of storage.Finally,we analyzed the performance of the algorithm from the aspects of approximation ratio,storage complexity and time complexity.