Streaming Algorithms For DR-submodular Maximization Under A Knapsack Constraint On The Integer Lattice

Submodular optimization is one of the important research subjects of combinatorial optimization.Because of diminishing marginal return property of submodular function,it has been widely studied and applied in computer,mathematics,economics and other fields.Earlier studies mainly focused on set submodular optimization.In order to solve practical problems of multi unit combinatorial auctions and the maximization of influence propagation,the definition of submodular function needs to be extended to integer lattice.When the data scale exceeds the storage space of a single computer,or dataset cannot be read into memory for one time,the streaming model has become an important technique to process massive data.In this dissertation,we study the DR-submodular maximization problem under a knapsack constraint on integer lattice based on streaming model.We maximize the DR-submodular function under a knapsack constraint.In this problem,data points arrive in the form of stream.Before a new set of data points arrive,we reserve an integer number of data points from the current ones until the knapsack constraint is exceeded or pass over the full dataset once.Under the assumption that the optimal value is known,we first design a MarginalRatio Thresholding(shorted to MRT)streaming algorithm with a binary search subroutine.Secondly,in order to remove the above assumptions,we pass over the data stream once to obtain the estimation of the optimal value.Based on this estimation,we run the MRT streaming algorithm when pass over the second time.Then,we adopt the dynamic updates to design a one-pass streaming algorithm—dynamic MRT algorithm.The approximate ratio of the algorithm is(1/3-?),the memory complexity is O(K log K/?)and the number of oracle queries of a single element is O(log2 K/?).Finally,we deal with the problem of maximizing the impact of weighted budget allocation on the use of dynamic MRT algorithm.We demonstrate the effectiveness of the algorithm through numerical experiments.