In this work, we study a $k$-Cardinality Constrained Regularized Submodular Maximization ( $k$-CCRSM) problem, in which the objective utility is expressed as the difference between a non-negative submodular and a modular function. No multiplicative approximation algorithm exists for the regularized model, and most works have focused on designing weak approximation algorithms for this problem. In this study, we consider the $k$-CCRSM problem in a streaming fashion, wherein the elements are assumed to be visited individually and cannot be entirely stored in memory. We propose two multipass streaming algorithms with theoretical guarantees for the above problem, wherein submodular terms are monotonic and nonmonotonic.

The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular (BP) functions with partial monotonicity under a streaming fashion. In this model, elements are randomly released from the stream and the utility is encoded by the sum of partial monotone suBmodular and suPermodular functions. The goal is to determine whether a subset from the stream of size bounded by parameter $k$ subject to the summarized utility is as large as possible. In this work, a threshold-based streaming algorithm is presented for the BP maximization that attains a $\mathrm{(}\mathrm{(}\mathrm{1}\mathrm{-}\kappa \mathrm{)}\mathrm{/}\mathrm{(}\mathrm{2}\mathrm{-}\kappa \mathrm{)}\mathrm{-}𝒪\mathsf{}\mathrm{(}\epsilon \mathrm{)}\mathrm{)}$-approximation with $𝒪\mathsf{}\mathrm{(}\mathrm{1}\mathrm{/}{\epsilon }^{\mathrm{4}}\mathsf{}{\log }^{\mathrm{3}}\mathsf{}\mathrm{(}\mathrm{1}\mathrm{/}\epsilon \mathrm{)}\mathsf{}\log \mathsf{}\mathrm{(}\mathrm{(}\mathrm{2}\mathrm{-}\kappa \mathrm{)}\mathsf{}k\mathrm{/}{\mathrm{(}\mathrm{1}\mathrm{-}\kappa \mathrm{)}}^{\mathrm{2}}\mathrm{)}\mathrm{)}$ memory complexity, where $\kappa$ denotes the parameter of supermodularity ratio. We further consider a more general model with fair constraints and present a greedy-based algorithm that obtains the same approximation. We finally investigate this fair model under the streaming fashion and provide a $\mathrm{(}{\mathrm{(}\mathrm{1}\mathrm{-}\kappa \mathrm{)}}^{\mathrm{4}}\mathrm{/}{\mathrm{(}\mathrm{2}\mathrm{-}\mathrm{2}\mathsf{}\kappa \mathrm{+}{\kappa }^{\mathrm{2}}\mathrm{)}}^{\mathrm{2}}\mathrm{-}𝒪\mathsf{}\mathrm{(}\epsilon \mathrm{)}\mathrm{)}$-approximation algorithm.