Note on Two-Stage BP Maximization
Maximizing the sum of a suBmodular and suPermodular function is called BP maximization. In previous literature, algorithms for BP maximization under various constraints have been proposed. However, approximation guarantees of these algorithms usually depend on the suBmodular and the suPermodular curvature, simultaneously. In this paper, we study the two-stage BP maximization subject to a matroid constraint, and design a replacement greedy algorithm whose guarantee depends only on the supermodular curvature.
Authors
- Chuchu Xu
- Hong Chang (ORCID: https://orcid.org/0000-0003-0828-5189)
- Donglei Du (ORCID: https://orcid.org/0000-0003-0111-8572)
- Xiaoyan Zhang (ORCID: https://orcid.org/0000-0002-2224-1484)
Institutions
- University of New Brunswick (CA)
- Nanjing Normal University (CN)
Publication Details
- Journal
- International Journal of Foundations of Computer Science
- Published
- 2025-08-14
- DOI
- https://doi.org/10.1142/s0129054125400040
- Primary Topic
- Fault Detection and Control Systems
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Natural Science Foundation of China
- Qinglan Project of Jiangsu Province of China
- Natural Sciences and Engineering Research Council of Canada