A Note on Maximizing Regularized Submodular Functions Under Streaming  

作　　者：Qinqin Gong Kaiqiao Meng Ruiqi Yang Zhenning Zhang 

机构地区：[1]Beijing Institute for Scientific and Engineering Computing,Beijing University of Technology,Beijing 100124,China

出　　处：《Tsinghua Science and Technology》2023年第6期1023-1029,共7页清华大学学报（自然科学版（英文版）

基　　金：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).

摘　　要：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.

关 键 词：submodular optimization regular model streaming algorithms threshold technique 

分 类 号：O17[理学—数学]