Efficient deterministic algorithms for maximizing symmetric submodular functions

doi:10.1016/j.tcs.2025.115312

	Efficient deterministic algorithms for maximizing symmetric submodular functions
	Wan, Zongqi 1,2; Zhang, Jialin 1,2; Sun, Xiaoming 1,2; Zhang, Zhijie 3,4
	2025-08-28
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	1046 页码:12
摘要	Symmetric submodular maximization is an important class of combinatorial optimization problems, including MAX-CUT on graphs and hyper-graphs. The state-of-the-art algorithm for the problem over general constraints has an approximation ratio of 0.432 [16]. The algorithm applies the canonical continuous greedy technique that involves a sampling process. It, therefore, suffers from high query complexity and is inherently randomized. In this paper, we present several efficient deterministic algorithms for maximizing a symmetric submodular function under various constraints. Specifically, for the cardinality constraint, we design a deterministic algorithm that attains a 0.432 ratio and uses O(kn) queries. Previously, the best deterministic algorithm attains ( a 0.385-e ratio and uses O kn(10 9e ) 20 9e-1) queries [12]. For the matroid constraint, we design a deterministic algorithm that attains a 1/3-e ratio and uses O(kn log e-1) queries. Previously, the best deterministic algorithm can also attain 1/3-e ratio but it uses much larger O(e-1n4) queries [24]. For the packing constraints with a large width, we design a deterministic algorithm that attains a 0.432-e ratio and uses O(n2) queries. To the best of our knowledge, there is no deterministic algorithm for the constraint previously. The last algorithm can be adapted to attain a 0.432 ratio for single knapsack constraint using O(n4) queries. Previously, the best deterministic algorithm attains a 0.316-e ratio and uses O(n3) queries [2].
关键词	Symmetric submodular maximization Deterministic algorithm Approximation algorithm
DOI	10.1016/j.tcs.2025.115312
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[62402110] ; National Natural Science Foundation of China[62325210] ; National Natural Science Foundation of China[62272441]
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:001501151900001
出版者	ELSEVIER
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/42308
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	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, Wuhan, Peoples R China 3.Fuzhou Univ, Ctr Appl Math Fujian Prov, Sch Math & Stat, Fuzhou, Peoples R China 4.Fuzhou Univ, 2 Xueyuan Rd, Fuzhou, Fujian, Peoples R China
推荐引用方式 GB/T 7714	Wan, Zongqi,Zhang, Jialin,Sun, Xiaoming,et al. Efficient deterministic algorithms for maximizing symmetric submodular functions[J]. THEORETICAL COMPUTER SCIENCE,2025,1046:12.
APA	Wan, Zongqi,Zhang, Jialin,Sun, Xiaoming,&Zhang, Zhijie.(2025).Efficient deterministic algorithms for maximizing symmetric submodular functions.THEORETICAL COMPUTER SCIENCE,1046,12.
MLA	Wan, Zongqi,et al."Efficient deterministic algorithms for maximizing symmetric submodular functions".THEORETICAL COMPUTER SCIENCE 1046(2025):12.