A Note on Maximizing Regularized Submodular Functions Under Streaming

Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guarantees. The submodularity was investigated to capture the diversity and representativeness of the utilities, and the monotonicity has the advantage of improving the coverage. Regularized submodular optimization models were developed in the latest studies (such as a house on fire), which aimed to sieve subsets with constraints to optimize regularized utilities. This study is motivated by the setting in which the input stream is partitioned into several disjoint parts, and each part has a limited size constraint. A first threshold-based bicriteria $\mathrm{(}\mathrm{1}\mathrm{/}\mathrm{3}\mathrm{,}\mathrm{2}\mathrm{/}\mathrm{3}\mathrm{)}$-approximation for the problem is provided.