Two-stage submodular maximization under curvature

Yanzhi Li (), Zhicheng Liu (), Chuchu Xu (), Ping Li (), Xiaoyan Zhang () and Hong Chang ()
Additional contact information
Yanzhi Li: University of Science and Technology of China
Zhicheng Liu: Beijing University of Technology
Chuchu Xu: Nanjing Normal University
Ping Li: Central Research Institute, 2012 Labs
Xiaoyan Zhang: Nanjing Normal University
Hong Chang: Nanjing Normal University

Journal of Combinatorial Optimization, 2023, vol. 45, issue 2, No 23, 16 pages

Abstract: Abstract The concept of submodularity has wide applications in data science, artificial intelligence, and machine learning, providing a boost to the investigation of new ideas, innovative techniques, and creative algorithms to solve different submodular optimization problems arising from a diversity of applications. However pure submodular problems only represent a small portion of the problems we are facing in real life applications. In this paper, we further discuss the two-stage submodular maximization problem under a $$\ell $$ ℓ -matroid constraint. We design an approximation algorithm with constant approximation ratio with respect to the curvature, which improves the previous bound. In addition, we generalize our algorithm to the two-stage submodular maximization problem under a $$\ell $$ ℓ -exchange system constraint.

Keywords: Two-stage submodular maximization; $$\ell $$ ℓ -matroid constraint; $$\ell $$ ℓ -exchange system constraint; Curvature (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01001-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:2:d:10.1007_s10878-023-01001-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01001-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().