A Semi-streaming Algorithm for Monotone Regularized Submodular Maximization with a Matroid Constraint

In the face of large-scale datasets in many practical problems, it is an effective method to design approximation algorithms for maximizing a regularized submodular function in a semi-streaming model. In this paper, we study the monotone regularized submodular maximization with a matroid constraint and present a single-pass semi-streaming algorithm using multilinear extension function and greedy idea. We show that our algorithm has an approximation ratio of \((\frac{(\beta -1)(1-\textrm{e}^{-\alpha })}{\beta +\alpha \beta -\alpha }, \frac{\beta (\beta -1)(1-\textrm{e}^{-\alpha })}{\beta +\alpha \beta -\alpha })\) $(\frac{(\beta -1)(1-{\text{e}}^{-\alpha })}{\beta +\alpha \beta -\alpha },\frac{\beta (\beta -1)(1-{\text{e}}^{-\alpha })}{\beta +\alpha \beta -\alpha })$ and a memory of O(r(M)), where r(M) is the rank of the matroid and parameters \(\alpha ,\beta >1\) $\alpha ,\beta >1$ . Specifically, if \(\alpha =1.18\) $\alpha =1.18$ and \(\beta = 9.784\) $\beta =9.784$ , our algorithm is (0.302, 2.955)-approximate. If \(\alpha =1.257\) $\alpha =1.257$ and \(\beta = 3.669\) $\beta =3.669$ , our algorithm is \((0.272\, 6,1)\) $(0.2726,1)$ -approximate.