KMS Of Academy of mathematics and systems sciences, CAS
| Stochastic greedy algorithms for maximizing constrained submodular plus supermodular functions | |
| Ji, Sai1,2; Xu, Dachuan1; Li, Min3; Wang, Yishui4; Zhang, Dongmei5 | |
| 2021-08-22 | |
| Source Publication | CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE
 |
| ISSN | 1532-0626 |
| Pages | 9 |
| Abstract | 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. |
| Keyword | approximation algorithm constrained stochastic greedy submodular plus supermodular maximization |
| DOI | 10.1002/cpe.6575 |
| Indexed By | SCI |
| Language | 英语 |
| Funding Project | 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 Research Area | Computer Science |
| WOS Subject | Computer Science, Software Engineering ; Computer Science, Theory & Methods |
| WOS ID | WOS:000687025000001 |
| Publisher | WILEY |
| Citation statistics | |
| Document Type | 期刊论文 |
| Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/59093 |
| Collection | 中国科学院数学与系统科学研究院 |
| Corresponding Author | Zhang, Dongmei |
| Affiliation | 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 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment