摘要
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(1/3,2/3/)-approximation for the problem is provided.
基金
This work was supported by the Beijing Natural Science Foundation Project(No.Z200002)
the National Natural Science Foundation of China(Nos.12001523,12131003,and 12101587)
the National Innovation and Entrepreneurship Training Program for College Students of Beijing University of Technology(No.GJDC-2022-01-39)
the China Postdoctoral Science Foundation(No.2022M720329).
