Improved deterministic algorithms for non-monotone submodular maximization

doi:10.1016/j.tcs.2023.114293

CSpace

	Improved deterministic algorithms for non-monotone submodular maximization
	Sun, Xiaoming 1,2; Zhang, Jialin 1,2; Zhang, Shuo 1,2; Zhang, Zhijie 3
	2024-02-12
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	984 页码:17
摘要	Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization.In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 - ??????(1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1/6 - ?????? approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints.
关键词	Submodular maximization Deterministic algorithms Derandomization Twin greedy Multiplicative updates
DOI	10.1016/j.tcs.2023.114293
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[62325210] ; National Natural Science Foundation of China[62272441]
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:001133492900001
出版者	ELSEVIER
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/38482
专题	中国科学院计算技术研究所
通讯作者	Zhang, Zhijie
作者单位	1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing, Peoples R China 2.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing, Peoples R China 3.Fuzhou Univ, Ctr Appl Math Fujian Prov, Sch Math & Stat, Fuzhou, Peoples R China
推荐引用方式 GB/T 7714	Sun, Xiaoming,Zhang, Jialin,Zhang, Shuo,et al. Improved deterministic algorithms for non-monotone submodular maximization[J]. THEORETICAL COMPUTER SCIENCE,2024,984:17.
APA	Sun, Xiaoming,Zhang, Jialin,Zhang, Shuo,&Zhang, Zhijie.(2024).Improved deterministic algorithms for non-monotone submodular maximization.THEORETICAL COMPUTER SCIENCE,984,17.
MLA	Sun, Xiaoming,et al."Improved deterministic algorithms for non-monotone submodular maximization".THEORETICAL COMPUTER SCIENCE 984(2024):17.