Stochastic greedy algorithms for maximizing constrained submodular plus supermodular functions

doi:10.1002/cpe.6575

CSpace

	Stochastic greedy algorithms for maximizing constrained submodular plus supermodular functions
	Ji, Sai 1,2; Xu, Dachuan 1; Li, Min 3; Wang, Yishui 4; Zhang, Dongmei 5
	2021-08-22
发表期刊	CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE
ISSN	1532-0626
页码	9
摘要	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.
关键词	approximation algorithm constrained stochastic greedy submodular plus supermodular maximization
DOI	10.1002/cpe.6575
收录类别	SCI
语种	英语
资助项目	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
WOS类目	Computer Science, Software Engineering ; Computer Science, Theory & Methods
WOS记录号	WOS:000687025000001
出版者	WILEY
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/59093
专题	中国科学院数学与系统科学研究院
通讯作者	Zhang, Dongmei
作者单位	1.Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China 3.Shandong Normal Univ, Sch Math & Stat, Jinan, Peoples R China 4.Univ Sci & Technol Beijing, Sch Math & Phys, Beijing, Peoples R China 5.Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, 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.