STOCHASTIC-LAZIER-GREEDY ALGORITHM FOR MONOTONE NON-SUBMODULAR MAXIMIZATION

doi:10.3934/jimo.2020085

CSpace

	STOCHASTIC-LAZIER-GREEDY ALGORITHM FOR MONOTONE NON-SUBMODULAR MAXIMIZATION
	Han, Lu 1; Li, Min 2; Xu, Dachuan 3; Zhang, Dongmei 4
	2021-09-01
发表期刊	JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION
ISSN	1547-5816
卷号	17 期号:5 页码:2607-2614
摘要	The problem of maximizing a given set function with a cardinality constraint has widespread applications. A number of algorithms have been provided to solve the maximization problem when the set function is monotone and submodular. However, reality-based set functions may not be submodular and may involve large-scale and noisy data sets. In this paper, we present the Stochastic-Lazier-Greedy Algorithm (SLG) to solve the corresponding nonsubmodular maximization problem and offer a performance guarantee of the algorithm. The guarantee is related to a submodularity ratio, which characterizes the closeness of to submodularity. Our algorithm also can be viewed as an extension of several previous greedy algorithms.
关键词	cardinality constraint non-submodular monotone greedy algorithm Set function maximization
DOI	10.3934/jimo.2020085
收录类别	SCI
语种	英语
资助项目	Natural Science Foundation of China[11871081] ; Natural Science Foundation of Shandong Province[ZR2019MA032]
WOS研究方向	Engineering ; Operations Research & Management Science ; Mathematics
WOS类目	Engineering, Multidisciplinary ; Operations Research & Management Science ; Mathematics, Interdisciplinary Applications
WOS记录号	WOS:000740705700018
出版者	AMER INST MATHEMATICAL SCIENCES-AIMS
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/59848
专题	中国科学院数学与系统科学研究院
通讯作者	Zhang, Dongmei
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China 2.Shandong Normal Univ, Sch Math & Stat, Jinan 250014, Peoples R China 3.Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing 100124, Peoples R China 4.Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China
推荐引用方式 GB/T 7714	Han, Lu,Li, Min,Xu, Dachuan,et al. STOCHASTIC-LAZIER-GREEDY ALGORITHM FOR MONOTONE NON-SUBMODULAR MAXIMIZATION[J]. JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION,2021,17(5):2607-2614.
APA	Han, Lu,Li, Min,Xu, Dachuan,&Zhang, Dongmei.(2021).STOCHASTIC-LAZIER-GREEDY ALGORITHM FOR MONOTONE NON-SUBMODULAR MAXIMIZATION.JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION,17(5),2607-2614.
MLA	Han, Lu,et al."STOCHASTIC-LAZIER-GREEDY ALGORITHM FOR MONOTONE NON-SUBMODULAR MAXIMIZATION".JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 17.5(2021):2607-2614.