Two-stage submodular maximization under curvature

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 l-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 l-exchange system constraint.