摘要
Submodular maximization is a significant area of interest in combinatorial optimization.It has various real-world applications.In recent years,streaming algorithms for submodular maximization have gained attention,allowing realtime processing of large data sets by examining each piece of data only once.However,most of the current state-of-the-art algorithms are only applicable to monotone submodular maximization.There are still significant gaps in the approximation ratios between monotone and non-monotone objective functions.In this paper,we propose a streaming algorithm framework for non-monotone submodular maximization and use this framework to design deterministic streaming algorithms for the d-knapsack constraint and the knapsack constraint.Our 1-pass streaming algorithm for the d-knapsack constraint has a 1/4(d+1)-∈approximation ratio,using O(BlogB/∈)memory,and O(logB/∈)query time per element,where B=MIN(n,b)is the maximum number of elements that the knapsack can store.As a special case of the d-knapsack constraint,we have the 1-pass streaming algorithm with a 1/8-∈approximation ratio to the knapsack constraint.To our knowledge,there is currently no streaming algorithm for this constraint when the objective function is non-monotone,even when d=1.In addition,we propose a multi-pass streaming algorithm with 1/6-∈approximation,which stores O(B)elements.
基金
supported in part by the National Natural Science Foundation of China(Grant Nos.62325210 and 62272441).
