Stochastic greedy algorithms for maximizing constrained submodular plus supermodular functions
文献类型：期刊论文
| 作者 | Ji, Sai4,5; Xu, Dachuan5; Li, Min3; Wang, Yishui2; Zhang, Dongmei1 |
| 刊名 | 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 |
| 语种 | 英语 |
| WOS记录号 | WOS:000687025000001 |
| 出版者 | WILEY |
| 源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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。