Stochastic greedy algorithms for maximizing constrained submodular plus supermodular functions

doi:10.1002/cpe.6575

	Stochastic greedy algorithms for maximizing constrained submodular plus supermodular functions
	Ji, Sai 4,5; Xu, Dachuan 5; Li, Min 3; Wang, Yishui 2; Zhang, Dongmei 1
刊名	CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE
	2021-08-22
页码	9
关键词	approximation algorithm constrained stochastic greedy submodular plus supermodular maximization
ISSN号	1532-0626
DOI	10.1002/cpe.6575
英文摘要	The problem of maximizing the sum of a constrained submodular and a supermodular function has many applications such as social networks, machine learning, and artificial intelligence. In this article, we study the monotone submodular + supermodular maximization problem under a cardinality constraint and a p-system constraint, respectively. For each problem, we provide a stochastic algorithm and prove the approximation ratio of each algorithm theoretically. Since the algorithm of the latter problem can also solve the former problem, we do some numerical experiments of the two algorithms to compare the time as well as the quality of the two algorithms in solving the former problem.
资助项目	Beijing Natural Science Foundation Project[Z200002] ; National Natural Science Foundation of China[11871081] ; National Natural Science Foundation of China[12001039] ; Natural Science Foundation of Shandong Province[ZR2020MA029] ; Fundamental Research Funds for the Central Universities, USTB[FRF-TP-20-074A1]
WOS研究方向	Computer Science
语种	英语
出版者	WILEY
WOS记录号	WOS:000687025000001
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/59092]
专题	中国科学院数学与系统科学研究院
通讯作者	Zhang, Dongmei
作者单位	1.Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China 2.Univ Sci & Technol Beijing, Sch Math & Phys, Beijing, Peoples R China 3.Shandong Normal Univ, Sch Math & Stat, Jinan, Peoples R China 4.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China 5.Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Ji, Sai,Xu, Dachuan,Li, Min,et al. Stochastic greedy algorithms for maximizing constrained submodular plus supermodular functions[J]. CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE,2021:9.
APA	Ji, Sai,Xu, Dachuan,Li, Min,Wang, Yishui,&Zhang, Dongmei.(2021).Stochastic greedy algorithms for maximizing constrained submodular plus supermodular functions.CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE,9.
MLA	Ji, Sai,et al."Stochastic greedy algorithms for maximizing constrained submodular plus supermodular functions".CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE (2021):9.