Deterministic streaming algorithms for non-monotone submodular maximization

doi:10.1007/s11704-024-40266-4

	Deterministic streaming algorithms for non-monotone submodular maximization
	Sun, Xiaoming 1,2; Zhang, Jialin 1,2; Zhang, Shuo 1,2
	2025-06-01
发表期刊	FRONTIERS OF COMPUTER SCIENCE
ISSN	2095-2228
卷号	19 期号:6 页码:12
摘要	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)-& varepsilon; approximation ratio, using O((B) over tilde log (B) over tilde/& varepsilon;) memory, and O(log (B) over tilde & varepsilon;) query time per element, where (B) over tilde = 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 - & varepsilon; 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 - & varepsilon; approximation, which stores O((B) over tilde )elements.
关键词	submodular maximization streaming algorithms cardinality constraint knapsack constraint
DOI	10.1007/s11704-024-40266-4
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[62325210] ; National Natural Science Foundation of China[62272441]
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems ; Computer Science, Software Engineering ; Computer Science, Theory & Methods
WOS记录号	WOS:001376567700009
出版者	HIGHER EDUCATION PRESS
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/41133
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Zhang, Shuo
作者单位	1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 100049, Peoples R China
推荐引用方式 GB/T 7714	Sun, Xiaoming,Zhang, Jialin,Zhang, Shuo. Deterministic streaming algorithms for non-monotone submodular maximization[J]. FRONTIERS OF COMPUTER SCIENCE,2025,19(6):12.
APA	Sun, Xiaoming,Zhang, Jialin,&Zhang, Shuo.(2025).Deterministic streaming algorithms for non-monotone submodular maximization.FRONTIERS OF COMPUTER SCIENCE,19(6),12.
MLA	Sun, Xiaoming,et al."Deterministic streaming algorithms for non-monotone submodular maximization".FRONTIERS OF COMPUTER SCIENCE 19.6(2025):12.