A Streaming Algorithm For Integer Lattice Submodular Maximization With A Cardinality Constraint

Submodular optimization problem is a kind of classical combinatorial optimization problem,as one of the hot research issues in combinatorial optimization and computer science,it also has important research value in many subjects such as management science and data mining.Classical submodular functions are defined on sets,and its submodularity are equivalent to diminishing return property.Although the set submodular function has submodularity,it cannot describe some special practical problems,such as the maximization of influence propagation,sensor placement and so on,so extend the definition of submodular functions to integer lattice.The rapid development of computer science and the internet accelerates the arrival of the era of big data,in face of massive data processing requirements,we design streaming algorithm to solve related problems.In the streaming algorithm,data arrives in the form of stream.During the running of the algorithm,only a small part of the current stored data can be accessed,and massive data can be processed in real time.In this dissertation we study the flow model of monotone submodular function maximization problem with cardinality constraint on integer lattice.Firstly,assuming that the optimal value is known,an offline algorithm is designed with the improved binary search algorithm as a subroutine.Secondly,when the optimal value is unknown,the whole data stream is traversed in advance.Since,we designed a two-passes algorithm.Then,in order to get a one-pass algorithm dynamically estimates the optimal value of the current arrival data constantly updated.Finally,a numerical experiment is carried out on the single traversal flow algorithm against the background of facility opening problem,and the experimental analysis proves the effectiveness of the flow algorithm.In this dissertation,the above three algorithms are theoretically analyzed by approximate ratio,time and spatial complexity.The approximate ratio of the single traversal flow algorithm is(1/2-?),the memory complexity is O(?-1k log k),and the queries complexity is O(e-2 log2 k)per element.